9
$\begingroup$

A week or two (or maybe more) ago, the following question was posted and then deleted just as I was getting to the end of my solution. Unfortunately I have now forgotten what my solution was going to be. I don't think the OP reposted it, so here is a slight variant of it.

A boy has 20 candies in his hand. He eats them one at a time, but each time he puts one in his mouth there is a chance he drops one of those remaining in his hand. That chance is $0.04n$ where $n$ is the number remaining (and independent of everything else). So after eating the first candy there is a 0.76 chance that he is left with only 18 candies in his hand. He never picks up dropped candies. Find the probability that he ends up eating $k$ of the candies.

Part of the fun is the elegance or otherwise of the solution. The series one needs to sum with a plodding approach is not difficult, there is just a (fairly obvious) trap for the overhasty. But it would be good to think of a more elegant approach. I am snowed under with work today, but will try to reconstruct my solution and post it as an answer tomorrow (I am on GMT+1, ie 5 hours ahead of EDT. I hope that is the correct jargon for time in NY.).

Oh, I nice plot always helps. A solution for the general case (replacing 0.04 by a constant $p=\frac{1}{M}$, where $M\ge N$, and 20 by $N$) and any resulting rules of thumb for what was needed for him to eat at least half or whatever would be good too. The more sophisticated could rattle off the related inference problem: assuming your prior belief is that $p$ is uniformly distributed over (1) $[0,1]$, (2) $[0,0.1]$, (3) $[0.9,1]$ (three separate cases) and you observe that he drops $k$, then what is the posterior distribution for $p$?

BTW, aged 66, I don't tend to get given homework. :)

And I don't mind solutions with a software element, provided there is an adequate explanation. Also I have put together three questions of varying difficulty because they are so closely related. So to be clear, I would welcome solutions covering just one of (1) the basic problem (first yellow background above) with 20 candies and $p=0.04$, (2) the more general case with $N$ candies and $p=\frac{1}{M}$, and (3) the inference question (the second yellow background).

$\endgroup$
4
$\begingroup$

Setup on recursion:

$p\left(n,i\right)$ probability that $i$ of $n$ candies are eaten.

To be found: $p\left(20,k\right)$.

$p\left(n,i\right)=0$ if $2i<n\vee i>n$

$p\left(0,0\right)=1=p\left(1,1\right)$

If $2i\geq n\geq2$ then: $$p\left(n,i\right)=0.04\left(n-1\right)p\left(n-2,i-1\right)+\left[1-0.04\left(n-1\right)\right]p\left(n-1,i-1\right)$$

I have an excel sheet with the outcomes for $n\leq20$.

Looking at the highest outcome: the probability that the boy will eat $15$ of $20$ candies is about $0.329869$.

$\endgroup$
  • $\begingroup$ +1 seems reasonable enough. He always eats at least 10. He cannot eat more than 20. Prob of a dropped candy varies from 0.04 to 0.76, so a crude mental calculation suggests around $10+10\cdot0.8/2=14$ as the expected number. What does your spreadsheet give as the expected number? $\endgroup$ – almagest Jun 28 '16 at 13:13
  • $\begingroup$ Yep (thanks). I have $p(20,14)=0.270699$ and $p(20,16)=0.202084$ together with $p(20,15)$ mentioned in answer as largest values. Taken together allready exceeding 80 percent. $\endgroup$ – drhab Jun 28 '16 at 13:18
  • $\begingroup$ Thanks. I am going to wait a while to see if anyone comes up with an answer to the supplementary questions ... (in the second patch of yellow background text) $\endgroup$ – almagest Jun 28 '16 at 13:20
  • $\begingroup$ I will get you the expected number within some minutes. Wise to wait some time. $\endgroup$ – drhab Jun 28 '16 at 13:20
  • $\begingroup$ Expected value: $14.819979$ $\endgroup$ – drhab Jun 28 '16 at 13:23
0
$\begingroup$

This is only a partial answer to (2), although it also confirms the existing answer for (1) and gives some explanation for choosing $p=\frac{1}{M}$ with $M\ge N$. I hope it may inspire someone else to come up with some new ideas that lead to a general solution.

(2) We start by looking at the pure probability problem for the general case of $N$ candies in the boy's hand initially and a probability of $pm$ that he drops a candy as he puts one in his mouth, where $m$ is the number remaining after he selects the one to put into his mouth. So we are trying to find $k=f(N,p)$ that he ends up eating $k$ of the candies. Since this answer is already rather long I will deal with the inference problem in part (2) in a separate answer.

Note that he must eat one for every candy he drops, so $k\le\frac{N}{2}$. Also it is possible that he does not drop any so $0\le k\le\frac{N}{2}$. The fairly obvious trap I mentioned in the question is that if he drops a candy as he eats his first candy then the number of candies is reduced by 2, not 1.

A little thought shows that we have the recurrence relation $$f(n,k)=p(n-1)f(n-2,k-1)+\left(1-p(n-1)\right)f(n-1,k-1)\ \ (*)$$ The first term on the RHS corresponds to his dropping a candy and the second term to his not dropping a candy. So the first term has $n$ reducing to $n-2$ and the second to $n-1$, whilst $k$ reduces to $k-1$ in both terms.

At this point it is perfectly feasible to use software to solve it for specific values. I wasted 10 minutes failing to enter the right boundary conditions into Mathematica's RecurrenceTable function and switched to a spreadsheet in LibreOffice (an open source MS Office) with the following results for $p=0.04,N=20$:

$\begin{array}{lllllllllll} 10 & 11 & 12 & 13 & 14 & 15\\ 0.000009 & 0.000936 & 0.017521 & 0.105922 & 0.270699 & 0.329869\\ & \\ 16 & 17 & 18 & 19 & 20\\ 0.202084 & 0.062766 & 0.009540 & 0.000640 & 0.000014\end{array}$

and hence $E(k)=14.82$, which agreed with @drhab the first time I ran the spreadsheet. Encouraging!

Plotted in Mathematica they become:

enter image description here

To deal with the general case we need to probe a little further. Obviously we can only manage $k=N$ by not dropping any candies, so $(*)$ becomes $$f(n,n)=(1-p(n-1)f(n-1,n-1)$$ which we can easily iterate to get $$f(N,N)=(1-p)(1-2p)\dots(1-(N-2)p)(1-(N-1)p)$$ note that the problem only makes sense if $p<\frac{1}{N-1}$. The product can be written in terms of the gamma function, or more conveniently a pochhammer symbol. But we will lose a little generality by taking $p=\frac{1}{M}$ (as stated in the question), so that the expression becomes $$f(N,N)=\left(1-\frac{1}{M}\right)\left(1-\frac{2}{M}\right)\dots\left(1-\frac{N-2}{M}\right)\left(1-\frac{N-1}{M}\right)$$ Since we are assuming $p<\frac{1}{N-1}$ we have $M\ge N$, every term in the product is positive and we have $$f(N,N)=(M-1)!\frac{1}{M^{N-1}(M-N)!}\ \ (**)$$ Note that gives the correct answer (1= certainty) for $f(1,1)$.

Looking at $k=1$, (*) and putting $g(n)=f(n,n-1)$ gives $$g(n)=(M-1)\frac{n-1}{M^{n-2}(M-n+2)!}+\frac{M-n+1}{M}g(n-1)\ \ (***)$$ and evidently $g(1)=f(1,0)=0$ (must always eat at least one), and $g(2)=f(2,1)=\frac{1}{M}$ (necessary and sufficient to drop one while eating first one). Continuing, as a check, $g(3)=f(3,2)$ is easily seen to be $\frac{3}{M}-\frac{1}{M^2}$ from first principles and the recurrence gives the same result. Continuing, we find $$g(4)=\frac{3}{4(M-2)}+\frac{9}{4M}-\frac{19}{2M^2}+\frac{6}{M^3}=\frac{3M^3-14M^2+25M-12}{(M-2)M^3}$$ which already seems fairly complicated (in either of the last two forms)!

So I decided to specialize to $M=N+5$ (which fits the original problem if $N=20$). That gives $$f(N,N)=\frac{(N+4)!}{(N+5)^{N-1}5!}$$ and $$g(n)=\frac{(N+4)(n-1)}{(N+5)^{n-2}(N+7-n)!}+\frac{N+6-n}{N+5}g(n-1)$$

No doubt one could press on a little, but I can't help feeling I am missing something.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.