I have the following exact sum for the expectation of an event
$$\sum_{m=0}^{nk} \sum_{j=1}^n (-1)^{j-1}\binom{n}{j} \binom{(n-j)k}{m} / \binom{nk}{m}$$
which is exactly correct but I want to give an upper bounding approximation that is easier to interpret. In particular, I want to see the expectations dependence on the parameter $k$. In simulation, it appears that as $k \rightarrow \infty$ we have that the sum tends towards $n \log n$. However, I am unsure how to show such a result analytically. My attempt has been to use some form of a stirling approximation on the binomial coefficients like
$$\binom{n}{k} \leq \frac{n^k}{k!}$$
which can reduce the summation in the following way
$$\sum_{m=0}^{nk} \sum_{j=1}^n (-1)^{j-1}\binom{n}{j} \frac{((n-j)k)^m}{m!} \cdot \frac{m!}{(nk)^m} = \sum_{m=0}^{nk} \sum_{j=1}^n (-1)^{j-1}\binom{n}{j} \left(1-\frac{j}{n}\right)^m$$
and from here maybe we can upper bound the $(1-j/n)^m$ to simplify further to a sum which depends only on $j$? Again comparing to simulation, it seems that when $k \ll \log n$ the sum will be something like $nk$ and for $k \gg \log n$ we will have the $n \log n$ (thus removing the dependence on $k$) but I can't seem to derive such a result.
Any help or advice would be greatly appreciated!
Best Answer
Actually we may simply compute this sum (and I guess that your expectation may be computed differently to give the answer in the below simplified form). We start with $1/{nk\choose m}=(nk+1)\int_0^1 x^m(1-x)^{nk-m}dx$ by the Beta function $B(a,b)=\Gamma(a)\Gamma(b)/\Gamma(a+b)$ formula. Next, we sum up over $m$ with fixed $j$ to get $$ \sum_{m=0}^{nk}\frac{(n-j)k\choose m}{nk\choose m}=(nk+1)\int_0^1 (1-x)^{jk}\sum{(n-j)k\choose m}x^m(1-x)^{(n-j)k-m}dx\\=(nk+1)\int_0^1(1-x)^{jk}\left(x+(1-x)\right)^{(n-j)k}dx=(nk+1)\int_0^1(1-x)^{jk}dx= (nk+1)\int_0^1 t^{jk}dt. $$ Then sum up over $j$ to get $$ \sum_{m=0}^{nk} \sum_{j=1}^n (-1)^{j-1}\binom{n}{j} \binom{(n-j)k}{m} / \binom{nk}{m}=(nk+1)\int_0^1\sum_{j=1}^n(-1)^{j-1}{n\choose j}(t^k)^jdt\\=(nk+1)\int_0^1(1-(1-t^k)^n)dt=(nk+1)\left(1-\frac1k\int_0^1(1-s)^ns^{1/k-1}ds\right)\\=(nk+1)\left(1-\frac{\Gamma(n+1)\Gamma(1/k)}{k\Gamma(n+1/k+1)}\right)=(nk+1)\left(1-\frac{1\cdot 2 \cdot 3\cdot \ldots n}{(1+1/k)(2+1/k)\ldots (n+1/k)}\right). $$ Now your observation follows, for example, from $$ \frac{\ell}{\ell+1/k}=\left(\frac{\ell}{\ell+1}\right)^{1/k}\cdot e^{O(1/(\ell^2 k))}, $$ thus multiplying against $\ell=1,\ldots,n$ we get $$ \frac{1\cdot 2 \cdot 3\cdot \ldots n}{(1+1/k)(2+1/k)\ldots (n+1/k)}=\frac{e^{O(1/k)}}{(n+1)^{1/k}}=\exp\left(-\frac{\log n+O(1)}k\right), $$ therefore in the $\log n=o(k)$ regime using $1-\exp(-t)\sim t$ for small $t=\frac{\log n+O(1)}k$ we indeed get $n\log n$ asymptotics for your sum.