1
$\begingroup$

I think this is a natural question but am not sure where to find resources.

Consider the possible multisets arising from choosing $n$ times an item from one of $k$ categories. We can represent one such multiset by a vector $\vec{x} = (x_1,\dots,x_k)$ with $\sum_i x_i = n$.

Question. I would like to upper-bound the quantity

$$ \sum_\vec{x} \frac{n!}{x_1! \cdots x_k!} x_1^{x_1} \cdots x_k^{x_k} $$

This is equivalent to

$$ k^n \mathbb{E} \left[ x_1^{x_1} \cdots x_k^{x_k} \right] $$

where the expectation is over $\vec{x}$ as the outcome of a uniform multinomial distribution ($n$ draws and $k$ equally likely categories). I'd rather not assume that either $k$ or $n$ is large with respect to the other (or assume both; both cases are interesting).

My approaches so far.

If we are sloppy about how many $x_i$ are nonzero (for instance if $n \gg k$) then we expect most cases have all $x_i > 1$, and we can use Stirling's approximation for all of the factorials. (If this is not the case, we have to be more careful and talk about only the nonzero $x_i$, so the below is not correct as stated, but hopefully can be modified.) We get that our sum is \begin{align} &\approx \sum_{\vec{x}} \frac{\left(\frac{n}{e}\right)^n \sqrt{2\pi n}}{\left(\frac{x_1}{e}\right)^{x_1} \cdots \left(\frac{x_k}{e}\right)^{x_k} \sqrt{\left(2\pi x_1\right)\cdots\left(2\pi x_k\right)}} x_1^{x_1} \cdots x_k^{x_k} \\ &= \frac{n^n}{(2\pi)^{(k-1)/2}} \sum_{\vec{x}} \frac{1}{\sqrt{x_1 \cdots x_k}} \end{align}

Perhaps this sum can be approximated by an integral or volume of some sort? (Again, it is over all vectors $\vec{x}$ consisting of natural numbers and summing to $n$.) But I'm not sure how to do so, it got messy fast for me.

Another thought I had is to say that "most" vectors $\vec{x}$ have each $x_i \approx \Theta\left(\frac{n}{k}\right)$ (again being careful about regimes where many $x_i = 0$), and go from there. But I couldn't bound the contributions from the "tail" well.

$\endgroup$
5
  • 1
    $\begingroup$ The generating function $f(x)=\sum_n n^n x^n/n!$ is equal to $1/(1+W(-x))$, where $W$ is the Lambert $W$-function. The denominator has a zero at $x=1/e$ which should enable you to get a good approximation to the coefficients of $f(x)^k$ by standard techniques (see, e.g., Flajolet and Sedgewick's Analytic Combinatorics). $\endgroup$
    – Ira Gessel
    Dec 5, 2014 at 18:52
  • $\begingroup$ @IraGessel, thanks, it is probably my naivete, but can you say how exactly $f(x)$ connects to the question (i.e. how this is useful)? I will see if I can hunt down the book, thanks. $\endgroup$
    – usul
    Dec 5, 2014 at 23:51
  • 2
    $\begingroup$ @usul, if $k$ is constant and we denote the $n$th quantity in question by $f_n$, then the generating function $F(y)=\sum_n f_n y^n/n!$ is equal to $1/(1+W(-y))^k$, so the coefficients of $F(y)$ can be estimated using aforementioned standard techniques. $\endgroup$
    – Liam Baker
    Dec 6, 2014 at 10:04
  • $\begingroup$ @LiamBaker, it took me a little while to see that $F(y)$ and $f(x)^k$ really were the same generating function, but now I think I understand. Thanks! $\endgroup$
    – usul
    Dec 6, 2014 at 19:40
  • $\begingroup$ In "A recurrence related to trees", Proc. of the AMS (1989), Knuth and Pittel have investigated the ``tree polynomials" $t_n(y)=n![z^n]1/(1+T(z))^y$ (where $T(z)=-W(-z)$) and in praticular given the first two terms of the asymptotic expansion for fixed $y$ $\endgroup$
    – esg
    Apr 23, 2015 at 19:00

0

Your Answer

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