half pills

You have a prescription to take one half of a pill per day for 20 days but the pharmacist (who is too busy to divide pills for you) gives you 10 whole pills in a bottle. On day 1, you remove a pill from the bottle, break it into two half pills, take one, and return the other half pill to the bottle.On all subsequent days you shake the bottle thoroughly and pour something out  whatever comes out first - either a half pill or a whole pill; if it' s a half pill you take it and you' re done for that day; if it' s a whole pill, you split it into two half - pills, take one, and put the other back in the bottle, exactly like you did on day 1. On day 20 there can be only one half pill left in the bottle, but on day 19 there are two possibilities : either there is one whole pill or there are two half - pills left in the bottle.What is the probability that there are two half - pills in the bottle on day 19?

Solution by Michael A. Gottlieb
One way to solve this problem exactly is to use a Markov chain, defining the bottle's state to be (w,h) where w and h are the numbers of whole and half pills in the bottle, respectively. The initial state is assumed to be (W,H).

W=3; (* change to 10 to solve the problem *)
H=0;

Since the total number of pills can only stay the same or decrease (w+h <= W+H), while the number of whole pills can only decrease (w<=W),  the states can be enumerated as follows:

	(W,H),          (W,H-1),      ...    (W,0),
	(W-1,H+1),  (W-1,H),      ...    (W-1,0),
	(W-2,H+2),  (W-2,H+1)   ...    (W-2,0),
	.
	.
	(0,H+W),    ...                         (0,0)
	
The total number of states is then

NS = (∑_(i=1)^(W+1))(H+i)

The index of state (w, h)  in this enumeration is

x[w_,h_] :=((∑_(i=1)^(W-w))(H+i+1)) + H-h+1

The transition probability from state (w0, h0) to state (w, h) is given by

p[w0_,h0_,w_,h_]:= 
Which[ w == w0 &&h == h0-1,        h0/(h0+w0), (* half pill drawn *)
	   w == w0-1 && h == h0+1, w0/(h0+w0), (* whole pill drawn *)
            w0+h0+w+h==0,                 1,                         (* no pills: absorbing state *)
            True,                                          0                             (* impossible transition *)
]

with which the state transition probability matrix is defined:

M=ConstantArray[0,{NS,NS}];
Do[ 
M[[ x[w,h],x[w0,h0] ]]= p[w0,h0,w,h],
{w0,0,W},{h0,0,H+W-w0 },{w,0,W},{h,0,H+W-w}
]
MatrixForm[M]

The transition probabilities after (2 W + H) - 2 transitions (days) are found by raising the transition probability matrix to the corresponding power,

MP=MatrixPower[M,2W+H-2];
MatrixForm[MP]

The answer is then given by the transition probability from the initial state (W,H), to the final state (0,2).

MP[[x[0,2],x[W,H]]]

Interestingly,  the answer can also be found in the fundamental matrix for M:

F=Inverse[IdentityMatrix[NS-1]- Take[M,{1,NS-1},{1,NS-1}]];
MatrixForm[F]

Since the initial state (W,H) is the first state in the enumeration (x[W,H]==1), the first column of the fundamental matrix gives the average number of times the bottle is in each of the non-absorbing states. Note that the sum of the first column equals 2W+H,  the number of days spent in the non-absorbing states, which is constant in this problem.

Sum[F[[i,x[W,H]]],{i,NS-1}]

Since each non-absorbing state can be visited only once on a particular day (when one of the possible states for that day must be visited), the average number of days spent in those states is equal to the probabilities of their being visited on that day. The only  states possible on the second-to-last day are (0,2) and (1,0), so the respective probabilities of their being visited on that day are

{F[[x[0,2],x[W,H]]],F[[x[1,0],x[W,H]]]}