Probability of remaining a whole pancake rather than two halves.

Question

A very interesting question. It is trivial for small number of pancakes but for 100 I was not able to find an analytical or manual way to figure out the probability. Thanks a lot in advance if you can share your ideas!

Suppose you have 100 pancakes to eat. Everyday you eat a half of a pancake. In this way after one day there will remain 99 whole pancakes and a half pancake. Suppose your choice of the pancake is random. That is, you are equally likely to pick any remaining pancake, no matter it is a whole pancake or a half pancake, to eat everyday. Formally, if there are $X$ whole pancakes and $Y$ half pancakes at the beginning of some day, then the probability of each piece of pancake to be picked is $\frac{1}{X+Y}$. Then what's the probability of the event that after $99\times 2 = 198$ days of eating, there will remain a whole pancake rather than 2 halves of pancakes?

Notice that the question might be interpreted in another way, as @Acccumulation noted in his answer. So please be careful about the interpretation.

For example, denote the index of the day by $k$, and the number of whole pancakes at (the end of) day $k$ as $X_k$ (i.e., after you eat the pancake), then $P(X_0 = 100) = 1$, $P(X_1 = 99) = 1$, $P(X_2 = 99) =1/100, P(X_2 = 98) = 99/100 $.

If we denote the number of half pancakes at (the end of) day $k$ as $Y_k$, then it's easy to see that $2X_k + Y_k + k = 200$ and $$P(X_{k+1} = X_k - 1) = \frac{X_k}{X_k+Y_k}, P(X_{k+1} = X_k) = \frac{Y_k}{X_k+Y_k}.$$ Or equivalently, $$P(X_{k+1} = X_k - 1) = \frac{X_k}{200-k-X_k}, P(X_{k+1} = X_k) = \frac{200-k-2X_k}{200-k-X_k}.$$ However, this relationship depends on both the values of $X_k$ and $k$, which is hard to use for recursion by hand. Does anyone have some ideas to do recursion or go in some other directions? Thanks a lot!

Answer 1

Here's a method that provides the exact answer $(0.14218003717754\ldots)$, which as a fraction in lowest terms has a numerator and denominator with $3189$ decimal digits each.

For convenient notation, we can represent $n$ pancakes by a string of $n$ numbers, where each number represents how many halves of the corresponding pancake are present, removing any $0$s as they occur. The procedure is then as follows:

1. Start with a string of $n\ 2\text{s}$ and repeat the following steps $2n-2$ times.
2. Choose a position in the string uniformly at random.
3. Subtract $1$ from the number in the chosen position.
4. If the subtraction gives $0$, then remove that element from the string.

The question equivalent to the OP's is whether the result of the procedure is the string $2$ (representing a whole pancake) or the string $11$ (representing halves of two different pancakes).

Let pS (where S is a string) denote the probability that repeating the steps 2-3-4 eventually reduces S to $2$. Then we find the following system of equations by constructing the relevant trees of possible paths, noting those that reach string $2$:

p2 = 1

p12 = (1/2)*p2
p22 = p12

p112 = (2/3)*p12
p122 = (1/3)*p22 + (2/3)*p112
p222 = p122

p1112 = (3/4)*p112
p1122 = (2/4)*p122 + (2/4)*p1112
p1222 = (1/4)*p222 + (3/4)*p1122
p2222 = p1222

p11112 = (4/5)*p1112
p11122 = (3/5)*p1122 + (2/5)*p11112
p11222 = (2/5)*p1222 + (3/5)*p11122
p12222 = (1/5)*p2222 + (4/5)*p11222
p22222 = p12222

p111112 = (5/6)*p11112
p111122 = (4/6)*p11122 + (2/6)*p111112
p111222 = (3/6)*p11222 + (3/6)*p111122
p112222 = (2/6)*p12222 + (4/6)*p111222
p122222 = (1/6)*p22222 + (5/6)*p112222
p222222 = p122222

etc.

Here's a picture for the case of p222, where the number over an arrow indicates the number of equally likely cases with only one of the cases shown (e.g. here 222 may become any one of the three equally likely 122, 212, or 221, and only 122 is shown, etc.):

Thus, the probabilities of interest (i.e. p22, p222, p2222, etc.) are all determined by the above equations, with initial condition p2 = 1. This system of equations can be written as the following recursion, with $n\ge1,\ 0\le i\le n-1$:

$$\begin{align}P_i^{(n)} &= \begin{cases} 1, & \text{if}\ \ n=1,\ i=0\\[2ex] {n-1\over n}P_0^{(n-1)}, & \text{if}\ \ n>1,\ i=0\\[2ex] {n-(i+1)\over n}P_i^{(n-1)}+{i+1\over n}P_{i-1}^{(n)}, & \text{if}\ \ n>1,\ 0<i<n-1\\[2ex] P_{n-2}^{(n)}, & \text{if}\ \ n>1,\ i=n-1.\\ \end{cases} \end{align}$$

Here $P_i^{(n)}=$pS$_i^{(n)}$, where S$_i^{(n)}$ is any string composed of $i+1\ 2s$ and $n-(i+1)\ 1s$, so the probability that answers the OP's question is $P_{n-1}^{(n)}$ with $n=100$.

These equations can be programmed (in Sage) as follows, using iteration rather than recursive function calls in order to compute the case $n=100$ in a reasonable amount of time ...

def next(L): # routine to be iterated   
# input the list L of n probabilities 
# output the list M of n+1 probabilities
    n = len(L) + 1
    M = [0]*n
    M[0] = L[0]*(n-1)/n
    for i in [1..n-2]: M[i] = L[i]*(n-i-1)/n + M[i-1]*(i+1)/n
    M[n-1] = M[n-2]
    return M

def prob(n): # iterate next() n-1 times, starting with L = [1]
# return the desired probability for a starting string of n 2s
    L = [1]
    for _ in [1..n-1]: L = next(L)
    return L[-1]

for n in [1..100]:
    p = prob(n) 
    print n, p.n(), p

Some output:

  1 1.00000000000000 1
  2 0.500000000000000 1/2
  3 0.388888888888889 7/18
  4 0.336805555555556 97/288
  5 0.305538888888889 54997/180000
  6 0.284236419753086 460463/1620000
  7 0.268560305649710 51185279267/190591380000
  8 0.256411353406832 200170674968477/780662292480000
  9 0.246639514750182 11369422537341929933/46097327708651520000
 10 0.238557094011412 6873027837417268175729/28810829817907200000000
 20 0.196966565034451             116 digits/116 digits
 50 0.161160193091085             793 digits/794 digits 
100 0.142180037177541            3189 digits/3189 digits
200 0.127470565382368           13921 digits/13921 digits
500 0.112388292456287           86903 digits/86904 digits

NB: Monte Carlo simulations verify these results to three decimal places for $n$ up to $100$.

---

NB: The above answer uses a recursion different from the "simpler" one mentioned by @lulu in a comment, but they are equivalent in the sense of yielding exactly the same probabilities. However, neither recursion allows a feasible computation of the case $n=100$ unless recursive function calls (and exponentially increasing execution times) can be avoided by using iteration instead -- and I was unable to do so with the "simpler" recursion. For reference, the following is an implementation (in Sage) of @lulu's recursion using recursive function calls, where $P(n,m)$ is the probability that a state $(n,m)$ (i.e. $n$ whole pancakes and $m$ halves) eventually reaches the state $(1,0)$ (i.e., one whole pancake and no halves):

$$\begin{align} P(n,m) &= \begin{cases} 0,&\text{if}\ \ m\ge0,n=0\\[2ex] \frac n{n+m} P(n-1,m+1)+\frac m{n+m} P(n,m-1), & \text{if}\ \ m>0,n>0\\[2ex] P(n-1,m+1),& \text{if}\ \ m=0,n>1\\[2ex] 1,&\text{if}\ \ m=0,n=1\\[2ex] \end{cases} \end{align}$$

def P(n,m):
    if n==0: return 0
    if n==1 and m==0: return 1
    if m==0: return P(n-1,m+1)
    return (n/(n+m))*P(n-1,m+1) + (m/(n+m))*P(n,m-1)

Now P(n,0) equals prob(n), but on my system the execution time for P(n,0) is at least $3.6$ times that for P(n-1,0), and P(100,0) would require more than $10^{45}$ hours (compared to less than $1$ second for the iterativeprob(100)).

Answer 2

If you interpret each half pancake as a distinct entity (and so you have 200 distinct entities), the probability you used up 99 whole pancakes after 198 days of eating is given by $\frac{100\choose 99}{200 \choose 198}=\frac{1}{199}$.

Answer 3

The question is imprecisely worded. Suppose we interpret as that there are essentially 200 half-pancakes, each one paired with a partner. Each day, you randomly pick a half-pancake to each. What's the probability that the two remaining half-pancakes are partners? We can choose the "first" half-pancake freely, and there's are 199 remaining half-pancakes, of which only one is the partner, so the chance is 1/199.

However, it could be interpreted as being that you randomly pick among the pancakes that have at least half remaining, and eat half of it. So in the first interpretation, each remaining half-pancake has the same probability of being eaten, but in the second interpretation, each pancake has the same probability of having half of it eaten. Thus, in the first interpretation, whole pancakes would be twice as likely as half pancakes to have half of them eaten, while in the second interpretation, they would have the same probability. In the second interpretation, we can view this as choosing which pancakes we'll eat the 199th and 200th days. If we make the same choice each time, then we had a whole pancake the 198th day. The probability that both choices are the same is 1/100.

Answer 4

If you choose each remaining half pancake with equal probability, then you are effectively creating a random sequence of $200$ half pancakes. Therefore, the probability of the $199$-th half pancake being from the same pancake as the $200$-th, is the same as the probability as the second half pancake being from the same pancake as the first: any considerations when looking at the sequence from the one end are of course completely symmetrical to considering the sequence from the other end (if I didn't tell you which was the first and last, you wouldn't know which end is which). And, since the probability of the second half coming from the same pancake as the first half is $\frac{1}{199}$, the probability of the $199$-th half pancake being from the same pancake as the $200$-th is also $\frac{1}{199}$.

However, it seems like each day you choose each remaining pancake with equal probability, whether it is still whole or not, and this introduces an asymmetry. In particular, since at any time the probability of choosing a pancake of which half is already eaten is still just as high as choosing a pancake that is still whole, you are more likely to 'finish' pancakes in comparison to the first situation where each half pancake is chosen with equal probability. Therefore, you can expect to get more pairs of half pancakes coming from the same pancake to occur subsequently, and therefore while the probability of the first two half pancakes coming from the same pancake is $\frac{1}{100}$, the probability of the last two halfs coming from the same pancake will be higher than that.

Another way of seeing this is as follows: suppose that near the end you are left with $3$ half pancakes, two of which are from the same pancake, i.e. you are left with $A1$, $A2$, and $B1$. Now, if each half pancake gets chosen with equal probability, then the probability of getting the two $A$'s as your last two halfs is $\frac{1}{3}$. However, now that we are choosing whether to take a half pancake from $A$ or $B$ with equal probability, the probability of getting the two $A$'s as your last two halfs in this situation is $\frac{1}{2}$.

OK ... so ... I don't see a quick way yet to calculate the probability under these conditions yet. Hmmm...

I did the calculations for $3$ pancakes, and found that while the probability of getting the first two half pancakes coming from the same pancake is of course $\frac{1}{3}$, the probability of the last two half pancakes coming from the same pancake is $\frac{7}{18}$ .. so yes, indeed a little higher than $\frac{1}{3}$

Answer 5

When you do it for $3$ pancakes, the end state will have $18$ whole or $36$ halves leading to a probability of whole $1/3$. There is no guarantee the probability will remain the same for $4$ or more pancakes.

Specifically, the argument of choosing $2$ halves out of total is incorrect as the same halves can be arrived via multiple paths.