The dance marathon problem

Question

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?

Answer 1

I'll lay out the starting steps; I hope that after that it won't be much work for you to fill in on your own.

To be clear, the process is that there are a succession of dances. At the start, $n$ couples are dancing. In each round, each couple is (independently) eliminated with probability $1/2$. So the probability of a couple being eliminated at time exactly $j$ is $2^{-j}$ and the probability that they are eliminated at time $j$ or sooner is $1-2^{-j}$.

We want the probability that, eventually, precisely one couple remains. It is convenient to run the process until everyone is eliminated. Then the probability that the first couple is eliminated at time precisely $k+1$, while everyone else is eliminated at time $k$ or earlier, is $2^{-k-1} (1-2^{-k})^{n-1}$. Summing on $k$, the probability that the first couple survives longer than all the others is $\sum_{k=1}^{\infty} 2^{-k-1} (1-2^{-k})^{n-1}$. Then multiply by $n$ to get the probability that some couple survives longer than all the others: $$\sum_{k=1}^{\infty} n 2^{-k-1} (1-2^{-k})^{n-1}.\quad (\ast)$$

Now, fix a positive real number $\theta$ and let $n$ go to infinity through numbers of the form $\theta 2^u$, for $u \in \mathbb{Z}$. So $(\ast)$ becomes $$\sum_{k=1}^{\infty} \theta 2^{u-k-1} \frac{(1-2^{-k})^{\theta 2^u}}{1-2^{-k}}.$$ Putting $\ell = k-u$, that's $$\sum_{\ell=-u+1}^{\infty} \theta 2^{-\ell-1} \frac{(1-2^{-\ell-u})^{\theta 2^u}}{1-2^{-\ell-u}}.$$ As $u \to \infty$, we have $(1-2^{-\ell-u})^{\theta 2^u} \to \exp(-\theta 2^{-\ell})$ and $1-2^{-\ell-u} \to 1$. So, naively taking limits term by term, we get $$g(\theta) = \sum_{\ell=-\infty}^{\infty} \theta 2^{-\ell-1} \exp(-\theta 2^{-\ell}).$$ Note that the sum is convergent: As $\ell \to \infty$, the first factor goes to $0$ and the second to $1$; as $\ell \to -\infty$ the second factor goes to $0$ much faster than the first blows up.

Of course, one has to justify taking limits termwise, but I think this is the level of exercise which is reasonable to leave to you.

---

Instead, let me say a few things to make the argument seem plausible.

First of all, a sanity check: $g(\theta) = g(2 \theta)$; just change $\ell$ to $\ell+1$. This is as it should be. (I don't know why Spencer insists that $\theta \in [1,2)$.)

Second, the effect is numerically quite small. I get a minimum of 0.721342 near $\theta = 1.3$ and a maximum of $0.721354$ near $\theta = 1.9$.

Finally, let me try to sketch the heuristic which convinced me the result was reasonable. I don't know if this will make sense to anyone but me. Let's imagine two marathons, which start out with $1.5 \cdot 2^u$ and $2^u$ people, for some large $u$. Very roughly, if we run the first one for a single dance, it will drop down to $1.5 \cdot 2^{u-1}$ people. Then, if we run the second one for one dance, it will drop down to $2^{u-1}$. If we keep going in this manner, the numbers keep jumping over each other while staying in fixed ratio, until we get down to small values, say $12$ and $8$. There is no reason the odds for $n=12$ and $n=8$ should be the same, so why should they be for $1.5 \cdot 2^u$ and $2^u$.

More carefully, but still heuristically, if we start with $1.5 \cdot 2^u$ people, the number of people at the next step is a distribution, centered at $1.5 \cdot 2^{u-1}$ but with standard deviation $\sqrt{1.5 \cdot 2^u}$. Think of it as $1.5 \cdot 2^u \cdot 2^{-1} \cdot (1 \pm 2^{-u/2})$. At the next step, $1.5 \cdot 2^u \cdot 2^{-2} \cdot (1 \pm 2^{-u/2})(1 \pm 2^{-(u-1)/2})$. And continuing down $1.5 \cdot 2^{u-k} \cdot (1 \pm 2^{-u/2})(1 \pm 2^{-(u-1)/2}) \cdots$. So the ratio between the two marathons is like $$1.5 {\Big (} (1 \pm 2^{-u/2})(1 \pm 2^{-(u-1)/2}) \cdots {\Big)}^2$$ where we truncate the product at some fixed power of $2$; perhaps at $1 \pm 16^{-1}$. As $u$ grows, that product stays bounded, so the ratio is still staying roughly fixed, not spreading out all the way between $0$ and $\infty$. So I still buy the argument of the paragraph above.