1
$\begingroup$

Hi all,

I am encountering a problem in calculating the sum of multinomial coefficients. The original problem is about a signal source with $k$ symbols under uniform distribution, i.e.

$p_0=p_1=\cdots=p_{k-1}= \dfrac{1}{k}$.

My problem is to find an appropriate string length $N$ with two concerns:

  • The probability that a string of length $N$ contains all $k$ symbols is very high.

  • The length of this string $N$ is very short.

The first concern requires me to find the probability that

$$\textrm{Pr}(N) = \frac{1}{k^{N}} \sum_{\substack{n_i\geq 1 \\\ n_0+n_1+\cdots + n_{k-1} = N}} \binom{N}{n_0~n_1~\cdots ~n_k}$$

The sum is of the multinomial coefficients without omitted symbols.

Since these two concerns push $N$ in opposite directions, I suggest maximizing $\textrm{Pr}(N)/N$ which goes to $0$ as $N \to \infty$ or $N\to 0$. However, I really don't know how to calculate $\textrm{Pr}(N)$ despite the above expression as a sum.

Any comments are appreciated.

$\endgroup$
3
  • $\begingroup$ Your term is a chimera between a multinomial coefficient written as a fraction and a multinomial coefficient written as a, well, multinomial coefficient. Or is it really a multinomial coefficient made out of factorials? $\endgroup$ Sep 26, 2011 at 2:00
  • $\begingroup$ You need to read what you wrote carefully and edit it to make more sense. As well as the problem darij noted, your paragraph about $f$ has no clear meaning. It might be better to omit commentary and just state the problem precisely. $\endgroup$ Sep 26, 2011 at 2:56
  • $\begingroup$ I edited the question to try to fix and clarify it. I hadn't understood the Pr(N)/N part before. $\endgroup$ Sep 28, 2011 at 2:54

3 Answers 3

1
$\begingroup$

The probability that a sequence does not contain all symbols is bounded above by the expected number of symbols omitted, $k (\frac{k-1}{k})^N \approx k \exp (\frac{-N}{k})$. You can ensure this is small by choosing $N$ to be large relative to $k \log k$.

You can get an exact probability easily using inclusion-exclusion since it is easy to count the sequences which omit a particular subset.

$$ \sum_{i=0} (-1)^i {k \choose i} \bigg(\frac{k-i}{k}\bigg)^N.$$

$\endgroup$
1
$\begingroup$

Here is how to estimate $$Q(n,t) = \sum \binom{n}{k_1,\ldots,k_t}$$ with the sum over $k_1,\ldots,k_t\ge 1$ such that $k_1+\cdots+k_t=n$. Let $X_1,\ldots,X_t$ be independent random variables with truncated Poisson distribution $$Pr(X_i=q) = (e^{\lambda}-1)^{-1}\frac{\lambda^q}{q!},~~~q\ge 1.$$ Define $X=\sum_{i=1}^t X_i$. Then $$Q(n,t) = n!~ \lambda^{-n} (e^\lambda-1)^t Pr(X=n).$$ This is true for any $\lambda>0$. Now adjust $\lambda$ until $n$ is the mean of $X$ (requires solving some equation which might not have a closed form solution) and apply the central limit theorem. Since each $X_i$ is log-concave, $X$ is log-concave too, so the CLT applies in a local sense. So $Pr(X=n)$ is asymptotic to $1/\sqrt{2\pi\sigma^2}$ where $\sigma^2$ is the variance of $X$ (which is of course $t$ times the variance of $X_i$).

$\endgroup$
0
$\begingroup$

Thanks for Dr. Kao and Dr. Zetterberg's paper

An Identity for the Sum of Multinomial Coefficients

it is published on MAA, Feb 1957.

The solution to my question is reached in a different way.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.