The lonesome king

This Riddler puzzle is about a random elimination game. Will someone remain at the end, or will everyone be eliminated?

In the first round, every subject simultaneously chooses a random other subject on the green. (It’s possible, of course, that some subjects will be chosen by more than one other subject.) Everybody chosen is eliminated. In each successive round, the subjects who are still in contention simultaneously choose a random remaining subject, and again everybody chosen is eliminated. If there is eventually exactly one subject remaining at the end of a round, he or she wins and heads straight to the castle for fêting. However, it’s also possible that everybody could be eliminated in the last round, in which case nobody wins and the king remains alone. If the kingdom has a population of 56,000 (not including the king), is it more likely that a prince or princess will be crowned or that nobody will win? How does the answer change for a kingdom of arbitrary size?

Here is my solution:
[Show Solution]

11 thoughts on “The lonesome king”

  1. Isn’t it surprising that the pattern doesn’t get washed out in the noise? I just reasoned from the 1/e observation and some initial values, because any major decay of the wave happens early on, before the law of large numbers kicks in, and there are only 10ish rounds to worry about. Great riddler.

    1. Yes it is surprising! My interpretation is that if you look at the distribution of where you’ll end up next move given your current position is n, the mean is n/e, but the variance is small enough that the distribution doesn’t get distorted as n gets large. Agreed — this was a great riddler and the solution I found was not at all what I was expecting to find.

  2. Here’s what I want to know: Why 1/2? The average of the limiting upper and lower bounds as n -> ∞ appears to be very close to 1/2 (although your data and mine both suggest that it’s really about 0.503). Is that just a coincidence?

    1. Great question — I also wondered about that. I suspect the oscillations continue on forever and the amplitude never dies out, but do they eventually become symmetric about 0.5, or will that 0.503 persist?

  3. Great solution. I wanted to show whether the exponentially increasing period is related to the fact that the expected number of remaining participants after one round is equal to n/e.

    I went for the brute force monte carlo solution with n=10,000. At each of the 10,000 games, I recorded the number of participants in each round. So in the first game, I recorded 56,000 for the first round, 20,679 for the 2nd round, 7585 for the 3rd, 2832 for the 4th, 1051 for the 5th, 375 for the 6th, 126 for the 7th, 46 for the 8th, 13 for the 9th, 3 for the 10th, and 1 for the 11th round, a successful game with a winner. I captured an overall histogram (with logarithmically sized bins) for the 10,000 games, plotted against the overall probability curve as a function of n, and posted to imgur, below. You can see that the distribution is cyclic corresponding to the subsequent rounds of each game, and repeatedly falls in a trough of the decaying oscillation.

    I hope this helps to illuminate the phenomenon underlying the ongoing oscillation.

    http://imgur.com/JOsijkE

  4. As always, I really enjoyed reading through your solution. Very insightful.

    I was curious if more progress could be made towards an analytic solution (or computing probabilities for n > 5000) with an explicit formula for the transition matrix. I found the following two formulas:

    1) A(m≥0,n≥m+2) = (n!/m!)/(n-1)^n * sum[!i/(i-1)! * {n-1, n-m}_i for i = 2:n-m]

    where !n is the subfactorial function and {n,k}_r is an r-restricted Stirling Number of the second kind.

    2) A(m≥0,n≥m+2) = (n-m)/(n-1)^n * C(n,m) * sum[(-1)^i * C(n-m-1,i) * (n-m-i)^(m+i-1) * (n-m-i-1)^(n-m-i) for i = 0 to n-m-2]

    where C(n,m) is the binomial function.

    In the first formula, the !i/(i-1)! term is approximately i*1/e for i > 3 which is consistent with the population decreasing by a factor of e each iteration. The second formula seems more opaque to me but is easier to compute because it avoids calculating the r-restricted Stirling numbers which are resource intensive.

    Anyway, do these formulas offer any other insights into the problem or provide a path to an analytic solution?

    1. Hmmm… I’m not sure. Although having a closed form expression for the transition matrix $A$ is nice, ultimately we need an efficient way of computing the top eigenvector of $A$, or an efficient way of computing powers of $A$. The reason this is computationally difficult is because the entries of $A$ get very small.

      The reason I couldn’t go beyond 5000 in my solution wasn’t because I couldn’t compute $A$ efficiently. In fact, the recursion I used to compute $A$ was fast enough to take me well beyond 5000. The problem was that the entries of $A$ got so small that they were zero to machine precision.

      1. Does that matter? I would have thought rounding them down to zero would not introduce significant error into the final result. I tried rounding to zero any entry less than 10^(-10) after every multiplication for N=100 (using Mathematica’s Chop command), and got the same final result to ten significant digits.

        As you probably know, the Riddler has now posted their answer (quoting your nice graph!). Apparently it’s been proven that the result oscillates forever, but the precise parameters of the oscillation are not known.

        As you’ve said, it’s a very surprising result. Amazing that such complexity can be hidden in such a simple algorithm.

Leave a Reply to MarkS Cancel reply

Your email address will not be published. Required fields are marked *