Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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? –  darij grinberg Sep 26 '11 at 2:00
    
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. –  Brendan McKay Sep 26 '11 at 2:56
    
I edited the question to try to fix and clarify it. I hadn't understood the Pr(N)/N part before. –  Douglas Zare Sep 28 '11 at 2:54
add comment

3 Answers

up vote 1 down vote accepted

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

share|improve this answer
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
2  
AMM, not MAA. Anyway I think you are looking for the Stirling numbers of the 2nd kind: en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind –  darij grinberg Sep 26 '11 at 3:59
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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