4
$\begingroup$

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!

$\endgroup$
3
  • 1
    $\begingroup$ In alternating sums, one-sided bounds like that do not work $\endgroup$ Commented Dec 8, 2021 at 17:03
  • $\begingroup$ Your post appears to contain at least two questions, depending on how $k$ and $\ln n$ compare to each other. It is better to have just one, quite specific, question per post. For one thing, this could make it more attractive to potential answerers. $\endgroup$ Commented Dec 8, 2021 at 17:08
  • $\begingroup$ @FedorPetrov this makes sense yes, is there any reasonable way of approximating this alternating sum then? $\endgroup$ Commented Dec 8, 2021 at 17:13

1 Answer 1

8
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I did not know this beta function relationship to binomial coefficients but the direct computation appears straightforward, thank you! Was the transition from x -> t -> just doing substitutions on the integration bounds? Sorry for pestering for the clarification. $\endgroup$ Commented Dec 8, 2021 at 21:31
  • 1
    $\begingroup$ $t=1-x$ (change of variables in the integral). $\endgroup$ Commented Dec 8, 2021 at 22:21

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.