# Taking random items out of a container with replacement

I take vitamins in the morning, but one of them I only take a half tablet.

So, I have an initial container with 100 full tablets, and every morning I take out a random tablet. If it's a full tablet, I break it in half, put half back, and take half. If it's a half tablet, I just take it. Given that, how many days must I do this before I get a $> 50\%$ chance of getting a half tablet? (Or, what's the % chance I get a half tablet after $X$ days?)

NB: This isn't homework; it just occurred to me as I was doing my morning routine, and I really have no idea where to start on trying to solve this. Pointers welcome. It feels like something with an infinite series, but I'm not sure.

-
Are you familiar with Polya's urn? It's a similar process, though not identical. –  cardinal Dec 11 '11 at 16:30
A few brief observations to get started: (1) Clearly if we start with $n$ tables, then after exactly $2n$ draws, there will be no tablets left; (2) The first time that you could possibly have $> 50\%$ chance is after $n/2$ draws and this happens with probability $\prod_{i=0}^{(n/2)-1} (1-\frac{i}{n})$; (cont.) –  cardinal Dec 11 '11 at 21:07
(cont.) (3) Let $(H_t,W_t)$ denote the ordered pair of half tablets and whole tablets after $t$ draws. Then, there are $\lceil(t+1)/2\rceil$ possibilities and they are $(2k,n-t/2-k)$ for $0 \leq k \leq t/2$ if $t$ is even and $(2k+1, n-(t+1)/2-k)$ for $0 \leq k \leq (t-1)/2$ if $t$ is odd. This works up to time $n$. After that the number of possibilities starts to shrink again, since there is the possibility we've already split all whole tablets. –  cardinal Dec 11 '11 at 21:12
Since the process $X_t = (H_t, W_t)$ is Markov (though not time homogeneous), and evolves according to a recombinant tree, then the probabilities of each outcome can be easily solved for recursively. I have not (yet) tried working out explicit solutions for each. –  cardinal Dec 11 '11 at 21:13
Note that until you draw a half-tablet: 1) there are always 100 items (= # tablets + # half-tablets) in the container, 2) Just before you make your $N^{th}$ draw, there are $N-1$ half-tablets in the container, one for each full tablet you've drawn so far and replaced with a half-tablet. –  jbowman Dec 11 '11 at 21:15

In a certain sense, the answer depends on how lazy you want to be.

If you are willing to do some very mild bookkeeping, then it is easy to calculate on any particular day the exact probability of select a half-tablet based on your previous draws. This is a form of conditional probability calculation. If you don't like to do any bookkeeping at all, then a marginal probability calculation can be obtained. The former gives a very simple expression, while the latter is more complicated. (This is the price you pay for additional laziness.)

A simple observation

Note that at any point in time, if we draw a whole tablet, then (i) the total number of tablets stays the same, (ii) the number of whole tablets decreases by one and (iii) the number of half-tablets increases by one.

Otherwise, if we draw a half-tablet, then the total number of tablets and the number of half-tablets both decrease by one, and the number of whole tablets stays the same.

Hence, knowing only the number of whole tablets chosen over the total number of days, we can calculate exactly how many half-tablets and whole tablets are left in the jar. Specifically, let $X_t$ be the number of whole tablets drawn up to time $t$ (inclusive). Then, the number of remaining whole tablets is $W_t = n - X_t$ and the number of half-tablets is $H_t = X_t - (t-X_t) = 2 X_t - t$. (The last quantity can be seen to arise from the $X_t$ half-tablets created by drawing each of the $X_t$ whole tablets and replacing them with a half-tablet minus the $t-X_t$ half-tablets we must have consumed.)

Conditional probability

Thus, by keeping track only of what day we are on and a running total of how many whole tablets we've drawn, we can find the conditional probability of drawing a half-tablet on day $t+1$ as $$\renewcommand{\Pr}{\mathbb P} \Pr( \text{draw half-tablet on day t+1} \mid (t,X_t) ) = \frac{H_t}{H_t+W_t} = \frac{2 X_t - t}{n - t + X_t} .$$

So, by using very simple bookkeeping, we can calculate the probability of drawing a half-tablet on each day for each individual realization of this process. In particular, this allows us to determine exactly the first day on which we have greater than 50% chance of drawing a half-tablet.

Unconditional (marginal) probability

If we are too lazy to keep track of how many whole tablets we've drawn (or simply don't have a pen), then we can completely ignore the past and rely on marginal probabilities of drawing a half-tablet. From the above observation, it's apparent that $H_t$ follows a time-imhomogenous Markov process satisfying $$H_{t+1} = \begin{cases} H_t - 1 & \mathrm{w.p.}\; H_t / (H_t + W_t) \\ H_t + 1 & \mathrm{w.p.}\; W_t / (H_t + W_t) \end{cases} \>.$$

We can, therefore, use a simple recursion to calculate $\mathbb P(H_t = h)$ for each valid $h$. Some $R$ code to implement the recursion is found below.

Results for $n=100$

When we start with $n = 100$ tablets, then the first time that we have over a 50% chance of getting a half-tablet is at $t = 90$, i.e., after 90 tablets have already been drawn from the bottle (or in other words, on the 91st day). The probability is $$\mathbb P(\text{half-tablet on 91st draw}) \approx 0.502571 \>.$$

Below is a graph of the probability of getting a half-tablet as a function of $t$.

Here is some very simple (and very inefficient!) $R$ code to calculate the probability of being in each state as a function of $t$. At the end is the calculation of the probability of drawing a half-tablet at each point in time.

# Eat-your-vitamins stochastic process
n <- 100
P <- matrix(0,n+1,2*n+1)

P[1,1] <- 1
for( t in 0:(2*n-1) )
{
j <- t + 1
offset <- 1 * (t %% 2 != 0)
M <- min(t,2*n-t)

for( h in seq(offset,M,by=2) )
{
i <- h + 1
w <- n - (h+t)/2
if( h > 0 )
P[i-1,j+1] <- P[i-1,j+1] + P[i,j] * h / (h+w)
if( w > 0 )
P[i+1,j+1] <- P[i+1,j+1] + P[i,j] * w / (h+w)
}
}

# Probability of getting a half-tablet as a function of time.
H <- matrix(0:n,nrow(P),ncol(P))
W <- n - H/2 - t(matrix(0:(ncol(P)-1),ncol(P),nrow(P)))/2
pr.half <- colSums( P*H/(H+W) )

-
Thanks cardinal; I'm in way over my head here, so I'm going to have to trust your maths. I'll go over it to see if I can understand what's going on, but I think my problem was much more easily stated than solved! Now, for x^k + y^k = z^k for x, y, z, and k > 2... ;-) –  Michael Campbell Dec 12 '11 at 17:10
There are a couple points I've thought of since I posted this which might help a bit with intuition. I'll edit them in to the post in a bit. –  cardinal Dec 12 '11 at 17:17
(+1) excellent answer. I like how it flattens out at step 198 to 199, then jumps up to 1 at 200 (which you can just pick out from your graph). –  G. Jay Kerns Jan 4 '12 at 3:20
@G.JayKerns: Thanks. At one point several weeks ago when I was thinking about this more, I thought I had worked out the explicity probability at times $2n-1$ and $2n-2$. The discontinuity is certainly intriguing and it might be fun to determine how it behaves as $n$ gets large. –  cardinal Jan 4 '12 at 3:40
(+1) Very nice answer! –  Elvis Jan 4 '12 at 8:31