Splitting a hundred dollar bill

This Riddler puzzle investigates a method for deciding who should get a $100 bill found on the ground. It leads to some interesting consequences…

You and four statistician colleagues find a \$100 bill on the floor of your department’s faculty lounge. None of you have change, so you agree to play a game of chance to divide the money probabilistically. The five of you sit around a table. The game is played in turns. Each turn, one of three things can happen, each with an equal probability: The bill can move one position to the left, one position to the right, or the game ends and the person with the bill in front of him or her wins the game. You have tenure and seniority, so the bill starts in front of you. What are the chances you win the money? What if there were N statisticians in the department?

Here is my solution to the first part, assuming five statisticians.
[Show Solution]

Here is my solution to the second part, assuming $N$ statisticians.
[Show Solution]

For the brave and curious, this next section explores connections between the problem and Fourier Transforms, complex analysis, and Chebyshev polynomials. Fair warning: advanced math!
[Show Solution]

12 thoughts on “Splitting a hundred dollar bill”

  1. I suppose for challenging problems like this one, people tend to grab the tools they are most comfortable with. My aim was to stick with Linear Algebra tools. (Shame on me for recognizing that the fundamental matrix for the markov chain was symmetric, but missing the circulant structure.)

    There is some very good stuff in this post… but no mention of Fibonacci numbers?? For better or worse, this led me to post my solution in full, below.

    My approach may seem a touch opaque, but it is a considerably simpler solution — no integrals or required use of the infinite.

    Here it is:

    Consider a function, f, that takes in some scalar, c, and a vector, x, and returns a scalar. Note that c = n // 2 (i.e. integer division of n, so for example, if n= 5, c = 2).

    here $f(c, x) = \left[\begin{matrix}1\\0\end{matrix}\right]^T * Y^{c} x $

    where $x = \left[\begin{matrix}x0\\x1\end{matrix}\right]$ and

    $Y = \left[\begin{matrix}3 & -1\\1 & 0\end{matrix}\right]$

    Note: we may also rewrite our function purely in terms of scalars as f(c, x0, x1)

    Eventually we will diagonalize Y, such that $Y^c = PD^{c}P^{-1}$

    Also note: Y looks kind of a like a demented fibonacci matrix, and indeed if you look at the output of:

    for c in range(1, somevalue):
    # not coincidentally, these are used in the final answer
    print f(c, x0= 1, x1 = 1)
    print f(c, x0= 0, x1 =-1)

    (edit: I could not get the indentation for the above code block to show up quite right.)
    you will actually recover the fibonacci numbers sequence.

    (Note: technically what follows applies to cases of having n being odd — a small tweak can adjust it for the case of n being even.)

    Now to go from all this to the final probability:
    First: The ‘raw frequency’ for the 0’th statistician to win is given by $f(c= n//2, x0=1, x1 =1)$ i.e. the first print stmt in the above for loop.

    The sum of the ‘raw frequencies’ for all the other statisticians to win is: $2*(c=n//2, x0= 0, x1 = -1)$ (i.e. the second print stmt in the above for loop, times 2). Note that we can use linearity and apply the 2 inside the function, but I left it outside as it makes things / underlying patterns easier to follow. It’s also worth remembering that when n is odd, setting aside the 0’th statistician, everyone has a ‘twin’ who has the exact same expectations, and that is what the scalar of 2 is for.

    So the probability that the zero’th statistician wins is $\frac{numerator}{denominator}$

    where $numerator = f(c= n//2, x0=1, x1 =1)$
    and $denominator = f(c= n//2, x0=1, x1 =1) + 2(c=n//2, x0= 0, x1 = -1)$

    Now. If you go through the effort of diagonalizing Y, and working through all of the algebra, you will get a closed form expression of

    prob player zero wins = $p(win) = \frac{- 3571 \left(- \sqrt{5} + 3\right)^{c} + 1597 \sqrt{5} \left(- \sqrt{5} + 3\right)^{c} – 1364 \left(\sqrt{5} + 3\right)^{c} + 610 \sqrt{5} \left(\sqrt{5} + 3\right)^{c}}{- 7985 \left(- \sqrt{5} + 3\right)^{c} + 3571 \sqrt{5} \left(- \sqrt{5} + 3\right)^{c} – 1364 \sqrt{5} \left(\sqrt{5} + 3\right)^{c} + 3050 \left(\sqrt{5} + 3\right)^{c}}
    $

    The above probably can be further simplified using closed form expressions for fibonnaci numbers, but further simplifying fractions is something for another day.

    Now that we have a nice finite closed form expression, we may take a limit and get

    $\lim_{c \to \infty}p(win) = – \frac{-682 + 305 \sqrt{5}}{-1525 + 682 \sqrt{5}}$

    which I realized is equivalent to the much simpler $\frac{1}{\sqrt{5}}$ only after reading your post. It is remarkable how useful this limit is — it is an extremely close approximation even for say N = 9 or N = 10.

      1. Yea… it looks like Rajeev nailed it. I suppose I’d express the solution for the odd numbers as:

        $\frac{F_n }{3 F_n – 2 F_{n-2}}$

        but this really is a distinction without a difference

      2. Right, if we notice that the Fibonacci sequence satisfies
        \begin{equation}
        F_{n+4}=F_{n+3}+F_{n+2}=2F_{n+2}+F_{n+1}=3F_{n+2}-F_n
        \end{equation}
        we see that the recursion $a_{n+2}=3a_{n+1}-a_n$ is fulfilled both by the odd-numbered $(1,2,5,13,…)$ and the even-numbered $(1,3,8,21,…)$ Fibonacci numbers, and consequently by any linear combination of these.
        Rajeev’s result follows then quite easily.

        1. and for what it’s worth, $\frac{3\mp\sqrt{5}}{2} = \left(\frac{1\pm\sqrt{5}}{2}\right)^2$, the square of the golden ratio and its negative inverse, which have the obvious connection to the Fibonacci sequence.

  2. Beautiful analysis as always!

    Here is yet another method of solution, which in some ways is a little simpler. Let’s generalize to the case that we pass left with probability x, right with probability y, and stop with probability 1-x-y. The probability of a total of L left passes and R right passes before stopping is

    p[L,R] = (1-x-y) x^L y^R n[L,R],

    where n[L,R] is the number of inequivalent arrangements of the passes; this number is (L+R)!/(L!R!), but we will not need this formula. Instead, all we will need to know is that the probabilities p[L,R] must sum to one, so it must be that

    Sum_(L,R) x^L y^R n[L,R] = 1/(1-x-y),

    where each sum runs from zero to infinity. To get x_k, the probability that the k^th statistician wins, we must sum only those probabilities for which L-R-k is a multiple of N. We can do this by inserting in the sum a factor of

    (1/N)Sum_(j=0 to N-1) w^(j*(L-R-k)),

    where w = exp(2 pi i/N). This sum equals one if L-R-k is a multiple of N, and vanishes otherwise (by usual properties of the roots of unity). Now we have

    x_k = (1-x-y)(1/N)Sum_(j=0 to N-1) Sum_(L,R) w^(-kj) (x w^j)^L (y w^-j)^R n[L,R].

    We already know how to do the sums over L and R, so we have

    x_k = (1-x-y)(1/N)Sum_(j=0 to N-1) w^(-kj)/(1 – x w^j – y w^-j).

    For the case x=y=1/3, this is the same as your result from the discrete Fourier transform.

  3. I like the closed form solution, but the first step — getting kth player winning probability for infinite n — can be simplified (though more complex solutions can also be informative).

    Let E(k) be the expected number times player k will get the bill. We have,
    E(0) = 1+E(1)*2/3 (since player 0 gets the bill initially and E(1)=E(-1))
    E(k) = 1/3*(E(k-1)+E(k+1)) (k>0)
    This is a linear homogeneous recurrence relation. The standard way of solving it is first finding solutions with E(k)/E(k-1) constant, say E(k)/E(k-1)=r. We have $r = 1/3+(1+r^2)$, with the solutions $r_1 = 3/2-\sqrt{5}/2$ and $r_2=3/2+\sqrt{5}/2$. Thus, $E(k) = c_1 k^{r_1}+c_2 k^{r_2}$. $c_2 = 0$ since $r_2>1$ and the sum of all E(k) is finite.
    $c_1 = E(0) = 1+E(1) 2/3 = 1+c_1 r_1 2/3$, so $c_1 = 3/\sqrt{5}$.
    Each time the player gets the bill, he keeps it with probability 1/3, so the probability that player k (the first player is 0) gets the bill is $E(k)/3 = 1/\sqrt{5} (3/2-\sqrt{5}/2)^k$.

    1. [the above comment with some markup fixed]
      I like the closed form solution, but the first step — getting kth player winning probability for infinite n — can be simplified (though more complex solutions can also be informative).

      Let E(k) be the expected number times player k will get the bill. We have,
      E(0) = 1+2/3*E(1) (since player 0 gets the bill initially and E(1)=E(-1))
      E(k) = 1/3*(E(k-1)+E(k+1)) (k>0)
      This is a linear homogeneous recurrence relation. The standard way of solving it is first finding solutions with E(k)/E(k-1) constant, say E(k)/E(k-1)=r. We have $r = frac{1}{3}(1+r^2)$, with the solutions $r_1 = 3/2-\sqrt{5}/2$ and $r_2=3/2+\sqrt{5}/2$. Thus, $E(k) = c_1 r_1^k+c_2 r_2^k$. Here, $c_2 = 0$ since $r_2>1$ and the sum of all E(k) is finite.
      $c_1 = E(0) = 1+\frac{2}{3} E(1) = 1 + \frac{2}{3} c_1 r_1$, so $c_1 = 3/\sqrt{5}$.
      Each time the player gets the bill, he keeps it with probability 1/3, so the probability that player k (the first player is 0) gets the bill is $E(k)/3 = \frac{1}{\sqrt{5}} (3/2-\sqrt{5}/2)^k$.

  4. Here is a different solution if we just want the first player win probability given n statisticians.

    First use symmetry to merge pairs of players that are at the same distance from you:
    you: probability 1/3 – keep the bill, 2/3 – move the bill
    each middle player: 1/3 keep, 1/3 move left, 1/3 move right
    rightmost player (odd n): 1/2 keep, 1/2 move (1/2 = 1/3+1/9+1/27+…).
    rightmost player (even n): 1/3 keep, 2/3 move

    Next, recursively merge the rightmost player with the player next to him. Let p be the probability that the rightmost player keeps the bill (and 1-p probability to move the bill to the neighbor).
    1/3 move right → 1/3*p keep, 1/3*(1-p) stay until the next round
    combined: 1/3 move left, 1/3+1/3*p keep, 1/3*(1-p) stay
    Eliminate stay by normalizing the other options to 1: (1/3+1/3*p)/(1/3+1/3+1/3*p) = (p+1)/(p+2) keep

    Final step (two players; if the second player has the bill, he keeps it with probability p and otherwise passes it to the first player):
    1/3 – keep, 2/3*p – drop (the second player keeps the bill), 2/3*(1-p) – stay
    Keep probability = 1/3/(1/3+2/3*p) = 1/(1+2*p)

    Computation of the probability that the first player keeps the bill (‘=’ is used as assignment):
    n is odd: p = 1/2
    n is even: p = 1/3
    repeat floor(n/2)-1 times: p = (p+1)/(p+2)
    return 1/(1+2p)

    Notes:
    * For n=5, the result is 5/11.
    * As n approaches infinity, p approaches (sqrt(5)-1)/2 (by solving the equation p=(p+1)/(p+2)), and the probability that the first player keeps the bill approaches 1/sqrt(5).
    * To get the winning probability of the kth player, we can repeatedly merge the first player with the second one, though we have to keep track of two probabilities (basically, transmission and reflection probability).
    * Given arbitrary time-independent probabilities for choosing the next player, the probability that the first player gets the bill can be found by considering $p_i$ — probability that player 1 gets the bill if the current player is i, and setting up a linear system in n variables (corresponding to one step) that relates the $p_i$.

    Fibonacci and Lucas Numbers:
    If p is a/b, the next p is (p+1)/(p+2) = (a+b)/(a+2b), so numerator1,denominator1,numerator2,denominator2,… form a Fibonacci recurrence.
    For odd n, this corresponds to the Fibonacci sequence ($F_1=1$,$F_2=1$,$F_n=F_{n-1}+F_{n-2}$): $p = F_{n-1}/F_n$, and the answer is $F_n/(F_n+2 F_{n-1}) = F_n/(F_{n+1}+F_{n-1}) = F_n/L_n$.
    For even n, this corresponds to the Lucas sequence ($L_1=1$,$L_2=3$,$L_n=L_{n-1}+L_{n-2}$): $p = L_{n-1}/L_n$, and the answer is $L_n/(L_n+2 L_{n-1}) = L_n/(L_{n+1}+L_{n-1}) = \frac{1}{5} L_n/F_n$.

Leave a Reply to D Cancel reply

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