Skip to main content
4 of 6
Commonmark migration

The Dance Marathon problem

In his book, "The Strange Logic of Random Graphs ", Joel Spencer describes the "Dance Marathon" problem:

Imagine $n$ couples at a Dance Marathon. Each dance each couple remains standing with independent probability one half. A couple that does not remain standing is removed from the competition. A couple wins the prize if at the end of some dance they are the only couple that remained standing. It may happen that none of the couples that began a dance remained standing, in which case the prize is not awarded. What is the probability $f(n)$ that the prize is awarded?

The surprising fact is that $\lim_{n\rightarrow \infty} f(n)$ does not exist. We have an exact formula $$f(n) = n\sum_{k=1}^{\infty}(1-2^{-k})^{n-1}2^{-k-1}$$ Imagine the marathon continuing until the winning couple also collapses and let $k$ be the number of dances completed by the winners. There are $n$ choices for the winning couple, $k$ can be any positive integer, the other $n-1$ couples all do not survive the first $k$ dances, and the winning couple survives the first $k$ dances and not the $k+1$-st dance. Now parametrize $n=2^{u}\theta$ with $u$ integral and $\theta\in[1,2)$. For $k=u+i$, with $i$ fixed and $u\rightarrow \infty$, $n(1-2^{-k})^{n-1}2^{-k-2}\sim\theta 2^{-i}e^{-2^{i}\theta}$. Set $$g(\theta)=\sum_{i=-\infty}^{+\infty}\theta 2^{-i}e^{-2^{i}\theta}$$ Some careful analysis gives that for $\theta$ fixed and $n=2^{u}\theta\rightarrow \infty$, $f(n)\rightarrow g(\theta)$ and simple calculation gives that $g(\theta)$ is not a constant.

I'm confused by some elementary details (doesn't $g(\theta)$ diverge as $i\rightarrow -\infty$?) and would like to learn more about the "careful analysis". Could anyone either point me to a complete proof of this result or (if it's straightforward) generate one?