16
$\begingroup$

I thought of the following probability problem, which seems to have an answer of 1/e, and wonder if someone has an idea as to how to prove this.

Suppose a man has a bottle of vitamin pills and wishes to take a half pill per day. He selects a pill from the bottle at random. If it is a whole pill he cuts it in half, takes a half pill, and puts the other half back in the bottle. If it is a half pill, he takes that. He continues this process until the bottle is empty. What is the expected maximum number of half pills in the bottle? If the bottle starts with n pills, and M is the expected maximum number of half pills, then M/n appears to tend to 1/e as n tends to infinity.

$\endgroup$
6
  • $\begingroup$ One thought is generating functions. If you define f(m,n) to be the expected maximum if you start with m whole pills and n half pills, then f(m,n)=(m/n)f(m-1,n+1)+(1-m/n)f(m,n-1), except that when m or n is zero then you have to change the right hand side. Whether that leads to anything useful I don't immediately see. $\endgroup$
    – gowers
    May 11, 2011 at 15:14
  • 2
    $\begingroup$ Do you have an idea of the result if the man takes quarters of pills: If a pill is whole, he breaks it into $1/2+1/4+1/4$, eats $1/4$ and puts $1/2$ and $1/4$ back, if it is a half-pill, he eats half of it and puts $1/4$ back if it is a quarter, he eats it. What are then the expected maximum numbers for half-pills and quarter-pills? $\endgroup$ May 11, 2011 at 15:33
  • $\begingroup$ Hello Roland. That's a very nice generalization. I'll think about that. ---Martin $\endgroup$ May 11, 2011 at 15:49
  • 1
    $\begingroup$ Based purely on the appearance of 1/e in a probability context and no thought at all, I'll wager $.50 and a Sprite that this problem can be mapped onto the secretary problem: en.wikipedia.org/wiki/Secretary_problem $\endgroup$ May 11, 2011 at 16:05
  • $\begingroup$ Any reason you go for that rather than the umbrella problem? $\endgroup$
    – gowers
    May 11, 2011 at 16:17

2 Answers 2

12
$\begingroup$

One way of solving the problem (probably not the easiest) is via the "differential equation method" (see eg the paper by Nick Wormald, entitled "The differential equation method for random graph processes and greedy algorithms", in Lectures on Approximation and Randomized Algorithms, pp. 73-155).

Suppose there are $n$ pills in the beginning. Let $$ P(\lceil tn\rceil) = \text{number of whole pills after $\lceil tn\rceil$ steps} $$ and $$ H(\lceil tn\rceil) = \text{number of half pills after $\lceil tn\rceil$ steps} $$

Clearly, $2P(\lceil tn\rceil) + H(tn) = 2n - \lceil tn\rceil$.

Moreover, let $p(t) = \frac1{n}P(\lceil tn\rceil)$, and define $h(t)$ similarly.

Now, given the state $S_{\lceil tn\rceil}$ of the system after $\lceil tn\rceil$ steps, observe that $$ \mathbb{E}[P(\lceil tn\rceil+ 1) ~|~ S_{\lceil tn\rceil}] = P(\lceil tn\rceil) - \frac{P(\lceil tn\rceil)}{P(\lceil tn\rceil) + H(\lceil tn\rceil)}. $$ This suggests that, up to negligible error terms, $p(t)$ satisfies the ODE $$ p'(t) = -\frac{p(t)}{p(t) + h(t)} $$ with initial condition $p(0) = 1$. Similalry, $h(t)$ satisfies $$ h'(t) = \frac{p(t)}{p(t) + h(t)}-\frac{h(t)}{p(t) + h(t)} $$ and $h(0) = 0$. With this it shouldn't be too difficult to get the maximum of $h(t)$.

$\endgroup$
6
  • 5
    $\begingroup$ Indeed, this system leads to dh/dp=(h-p)/p, which has the closed form solution h(p)=-p log(p). The maximum of h occurs when p=h, which leads to log(p)=-1. $\endgroup$ May 11, 2011 at 15:35
  • $\begingroup$ I don't know that method, and obviously I don't expect you to explain it all for me, I guess I'll have to go read up on it if I'm that curious. But I am a bit puzzled: what's the idea that allows us to transition from purely describing the state of the system to talking about expectations? I mean, I see the expectations show up, but, informally, why does it work? Thanks in advance! $\endgroup$ May 11, 2011 at 15:40
  • $\begingroup$ Konstantinos and Michael, a very nice solution. Thank you. ---Martin $\endgroup$ May 11, 2011 at 16:30
  • 2
    $\begingroup$ Informally, it's because both $P$ and $H$ are nicely behaved in the sense of only a small change at each step. Now if they were true random walks with independent steps, we'd expect them to be very highly concentrated around their expectations at each step. So concentrated, in fact, that we could just take the union bound over all $n$ steps to show they always were close to their mean. The actual situation is even better, in that the walks are self correcting--if $P$ is unusually large at some step, it's more likely to go down in the next step. So we should expect concentration still. $\endgroup$ May 11, 2011 at 17:24
  • 2
    $\begingroup$ To clarify one thing: This "self-correcting" aspect isn't necessary for the Diff. Eq. method to work, though it does make things more intuitive. In general, you can imagine that even if the diff eq. leads to a positive feedback system instead of a negative one, it won't be noticable until you've already strayed pretty far from the expectation (assuming the diff. eq. giving the expectation doesn't blow up), so doesn't really have an impact on things. $\endgroup$ May 11, 2011 at 18:17
12
$\begingroup$

The problem is equivalent to the following: Suppose there are $n$ bins, and repeatedly, we throw balls which fall in one of the bins (uniformly and independently of the history). What is the maximum number of bins with exactly one ball? In the model with the pills, it is explicitly forbidden to draw a pill which has been drawn twice already, but for the current question, this clearly doesn't matter.

We can replace discrete time with continuous time, and throw the balls at the events of a Poisson process. This way, the balls falling in a particular bin arrive according to a Poisson process, and different bins are independent. If the problem was to determine the time $t$ to maximize the expected number of bins with exactly one ball at time $t$, then the answer would clearly be to choose $t$ so that the expected number of balls in a bin is 1, and the probability of having exactly one ball would be $1/e$ (we are maximizing $xe^{-x}$).

By the law of large numbers, the number of bins with exactly one ball will very likely be about $n/e$ at that time. To conclude that $M/n$ converges to $1/e$ in probability, it only remains to show that "exceptional times" with unusually many bins of exactly one ball are not likely to occur. I guess this can be established by quantifying the idea that if at time $t$ there are substantially more than $n/e$ bins with exactly one ball, then most likely there will continue to be so in a time interval after $t$, which is unlikely.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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