3 ms·
Let c_{n,m} be the expectation value of the number of remaining half pills starting from n whole pills and m half pills. Then we get the following recursion: c
by leni536 7y ago
Let c_{n,m} be the expectation value of the number of remaining half pills starting from n whole pills and m half pills. Then we get the following recursion:
c_{n,m}=n/(n+m) c_{n-1,m+1} + m/(n+m) c_{n,m-1}
Boundary condition: c_{0,m} = m
After some experimenting I got the following closed form solution: c_{n,m}=H_n+m/(n+1) where H_n=sum_{i=1}^n 1/i (nth harmonic number). This can be shown by induction. We want to know what happens if we start from n whole pills and 0 half pills: c_{n,0} = H_n. Indeed, they are the harmonic numbers.
- kkleindev 7y agoThanks for the hint! I wrote this up a little more explicitly: http://kevinkle.in/jekyll/update/2019/09/23/breaking_pills.html http://kevinkle.in/jekyll/update/2019/09/23/breaking_pills.h...
- sweezyjeezy 7y agoA slightly more intuitive argument. If you have a half pill and k - 1 whole pills remaining, then because we stop once all the whole pills are broken, then thinking about the order in which the pills will get picked next/again, by symmetry the probability that the half pill will remain at the end (i.e. be the last one to get picked next/again) is 1 / k. If p_k is the k'th last pill broken (so p_n is the first pill), then because at the point p_k is broken there are k - 1 whole pills remaining we get E[N] = sum_k (probability p_k has half a pill remaining at the end) = sum_k (1 / k)