3
$\begingroup$

What is a method to compute the asymptotics of a sum resulting from the inclusion-exclusion principle? Each term of the sum can be approximated perhaps by Stirling's formula or the Gaussian distribution. However the alternating sign should effect some cancellation. As an example, the answer to this combinatorial problem generates a probability $$p=\frac c{n\choose j},$$ where $$c=\sum_{k=w}^j(-1)^{k-w}(j-k+1){n-k+1\choose j-k+1}.$$ What is the asymptote of $p$ for $\big|\frac jn-a\big|=o(n)$ and $\big|\frac wn-b\big|=o(n)$ for some positive numbers $a$ and $b$ as $n\rightarrow\infty$?

$\endgroup$
  • 2
    $\begingroup$ It is an alternating sum with terms in decreasing size so the first term gives an upper bound and the first minus the second gives a lower bound. That might be tight enough for an answer. If not, use more terms for tighter bounds. $\endgroup$ – Aaron Meyerowitz Apr 6 at 4:57
  • $\begingroup$ @AaronMeyerowitz: You are right. Upvoted. I thought of that as well, but wondered if there might be tighter bounds and slicker in form. $\endgroup$ – Hans Apr 6 at 18:53
2
$\begingroup$

Another way to approach this from the generating function perspective. Notice that $$\sum_{k=l}^u (-1)^k [x^k]\, f(x) = [x^u]\,\frac{f(-x)}{1-x} - [x^{l-1}]\,\frac{f(-x)}{1-x},$$ and so the question reduces to studying the asymptotic of the coefficients of $\frac{f(-x)}{1-x}$.

In your example, we have $$(j-k+1)\binom{n-k+1}{j-k+1} = (n-j+1)\,[x^{j-k}]\,(1-x)^{-(n+2-j)}$$ and thus \begin{split} c &=\sum_{k=w}^{j} (-1)^{k-w} (j-k+1)\binom{n-k+1}{j-k+1} \\ &= (n-j+1)(-1)^{j-w} \sum_{t=0}^{j-w} (-1)^t\,[x^t]\,(1-x)^{-(n+2-j)} \\ &= (n-j+1)(-1)^{j-w}\,[x^{j-w}]\,\frac{1}{(1+x)^{n+2-j}(1-x)} \\ &= (n-j+1)\,[x^{j-w}]\,\frac{1}{(1-x)^{n+2-j}(1+x)}. \end{split}

Now, noticing the partial fraction decomposition $$\frac{1}{(1-x)^m(1+x)} = \frac{2^{-m}}{1+x} + \sum_{i=0}^{m-1} \frac{2^{-(i+1)}}{(1-x)^{m-i}},$$ we obtain the formula: $$c=(n-j+1)\left(\frac{(-1)^{j-w}}{2^{n+2-j}} + \sum_{i=0}^{n+1-j} \frac{1}{2^{i+1}}\binom{n+1-i-w}{j-w}\right).$$ Here all terms in the sum are positive and thus are more amenable to asymptotic analysis. For example, we can deduce $$\frac{n-j+1}{2}\binom{n+1-w}{j-w} \lesssim c \lesssim (n-j+1)\binom{n+1-w}{j-w}.$$

$\endgroup$
  • $\begingroup$ Very nice. But it seems you have not finished it. Are you not going to give some asymptotic analysis, via perhaps complex analysis, to the last expression for $c$? $\endgroup$ – Hans Apr 6 at 21:39
  • $\begingroup$ My answer got posted prematurely (misclick?) and is indeed unfinished. For the rest, I was going to use Lagrange Inversion but had to abandon my answer due to lack of time. I leave it as is now, and will get back to it later. $\endgroup$ – Max Alekseyev Apr 6 at 21:58
  • 1
    $\begingroup$ Meanwhile, I can give a reference to Section 5 in Generatingfunctionology for basic asymptotic analysis methods for g.f. coefficients. $\endgroup$ – Max Alekseyev Apr 6 at 22:29
  • $\begingroup$ I have completed my answer using partial fraction decomposition, which works better than Lagrange inversion here. $\endgroup$ – Max Alekseyev Apr 7 at 18:07
  • $\begingroup$ I’m not sure that the precision of the final result $U/2 \lt c \lt U$ justifies all machinery. Your upper bound $U$ looks like another way to write the first term (which is indeed an upper bound) . Then the first two terms give a lower bound of $(1-j/n)U.$ I suppose it depends on the size of $j/n.$ one can also use a few more terms in that case. $\endgroup$ – Aaron Meyerowitz Apr 7 at 18:40
2
$\begingroup$

Many unsolved asymptotics problems can be written as inclusion-exclusion sums. There is no general method for solving them.

However, in your case the terms decrease in absolute value and nearly form a geometric series. This is an easy case.

If $t_k$ is the $k$-term, then $t_{w+i}\approx (-1)^i (j/n)^i t_w$, so $$c \sim \frac{t_w}{1+j/n}.$$ To get rigorous bounds, you can use the fact that the partial sums of an alternating series with absolutely decreasing terms alternate above and below the full sum.

$\endgroup$
1
$\begingroup$

Your question seems extremely general! Perhaps the most famous result of this type states that the number of fixed points of the $N$-letter permutations $$\chi:S_N\to\mathbb N,\quad,\quad\chi(\sigma)=\#\{i|\sigma(i)=i\}$$ becomes Poisson (1) in the $N\to\infty$ limit. The proof uses the inclusion-exclusion principle at fixed $N\in\mathbb N$, and then some simple asymptotics in the limit. All this generalizes the fact that $$\mathbb P(\chi(\sigma)=0)\simeq\frac{1}{e}$$ in other words that "a random permutation is a derangement with probability about $1/e$''. All beautiful mathematics all this, you can take a look at papers by Diaconis et al. for more.

$\endgroup$
  • $\begingroup$ Could you please give a few specific references of the result in your answer? Thanks. $\endgroup$ – Hans Apr 6 at 23:28
  • $\begingroup$ en.wikipedia.org/wiki/Derangement $\endgroup$ – Richard Apr 7 at 10:20
  • $\begingroup$ What about the relevant Diaconis et al. papers? Thanks. $\endgroup$ – Hans Apr 7 at 16:24
  • $\begingroup$ No idea, don't remember.. but you can follow the wikipedia links, some of them probably lead into OEIS, with more links, do some Google too, and so on. $\endgroup$ – Richard Apr 7 at 17:33
  • 1
    $\begingroup$ @Hans may be Diaconis papers mentioned here: mathoverflow.net/questions/320497/… $\endgroup$ – Alexander Chervov Apr 7 at 18:29
1
$\begingroup$

The limiting probability is $0$ and it goes there pretty rapidly if we fix the ratios $\frac{j}n \approx a \lt 1$ and $\frac{w}n \approx b \gt 0$ and then let $n$ grow. In fact $p\lt n a^{w} \approx n{a}^{bn}$

This is a kind of cheap way out of the interesting problem of estimating $c$ but that is how it is.

The convergence to $0$ is pretty apparent from numerical experiments, however here is a calculation:

$$c\lt j\binom{n-w+1}{j-w+1}=j\frac{(n-w+1)!}{(j-w+1)!(n-j)!}$$

so $$\frac{c}{\binom{n}{j}} \lt j\frac{(n-w+1)!j!}{n!(j-w+1)!}=j\frac{j(j-1)(j-2)\cdots(j-w+2)}{n(n-1)(n-2)\cdots(n-w+2)} $$

since $a=\frac{j}{n} \gt\frac{j-k}{n-k}$

$$\frac{c}{\binom{n}{j}} \lt j(a)^{w-1}\approx na^w. $$

$\endgroup$
  • $\begingroup$ What does the symbol $(j)$ mean? Does $(j)=j$? Should it not be $j-w+1$ if you just take the first term in the sum? $\endgroup$ – Hans Apr 7 at 16:29
  • $\begingroup$ I started with $(j+w-1)$ but realized that for the inequality it came out cleaner to use $j*w-1 \lt j$ . $\endgroup$ – Aaron Meyerowitz Apr 7 at 16:59
  • 1
    $\begingroup$ I actually think it would be cleaner to use $j+w-1$ as it cancels with the same on the denominator and factors out $n-w+1$ on the numerator. But I suppose it does not make much of a difference. $\endgroup$ – Hans Apr 7 at 17:51
  • $\begingroup$ True, that might be cleaner. Instead of replacing $an-w+1$ by $an$ one could cancel and then replace $n-w+1$ by $n$ . But as you say, it doesn’t matter too much. $\endgroup$ – Aaron Meyerowitz Apr 7 at 18:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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