Restriction sum of multinomial coefficients

Question

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.

Answer 1

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.$$

Answer 2

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$).

Answer 3

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.