Consider $p(n)$ defined recursively by $p(1)=1$ and

$\displaystyle p(n)=\frac{1}{(n-1)^n}\sum_{i=1}^{n-1}\left\{\sum_{j=i}^{n-1}(-1)^{j-i}{n \choose j}{j\choose i}(n-j)^j(n-j-1)^{n-j}\right\}p(i)$.

What is the asymptotic behavior of $p(n)$ when $n\to+\infty$?


The function arises from the following process (similar to this paper "How to Select a Loser"):

Consider $n$ people, each round everyone randomly nominates a person other than herself (equally likely). Whoever gets nominated would be eliminated. What is the probability that this process ends up with only one person (vs. none left)?

Easy to see $p(2)=0$ and the expression above in the curly parentheses is the number of ways that after first round, $i$ people remain (inclusion-exclusion principle).

Numerical evidence indicates that $p$ does not converge and oscillates near $0.5$ with an extremely small amplitude. Indeed this has been shown for similar processes (in the paper above or a previous discussion here), but the technique described there does not seem to be straightforward applicable.

I am also interested in the asymptotics of the number of rounds. Numerically it behaves as $\log(n)+1/4+$ some tiny oscillatory term.

Would greatly appreciate any pointer to the existing literature.


Your Answer

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

Browse other questions tagged or ask your own question.