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 recursive functions.   Define the bottle’s state to be (w,h) where w and h are the numbers of whole and half pills in the bottle, respectively,  define the initial state to be (W,H) and the final state to be (0,2). This method works by walking the tree of possible states from initial to final, multiplying and adding transition probabilities as it goes from state to state. I provide two variants - one that caclulates the probability numerically, and another that shows the sequence of primitive operation used.

The algorithm is easy to describe in natural language:  R[w,h] returns the probability of starting in state (w,h) and ending in state (0,2) having no whole pills and two half pills.  So R[0,2] = 1; this defines the stopping condition for the recursion. Let p = 0; this will be the probability returned R[w,h]. If w>0 it is possible to draw a whole pill, resulting in the state (w-1,h+1), so  add to p the probability of drawing a whole pill w/(w+h) times R [w-1,h+1]. If h>0 it is possible to draw a half pill,  resulting in the state (w,h-1),  so add to p the probability of drawing a half pill h/(w+h) times R[w,h-1]. FInally, R(w,h) returns p.

Rn[w_,h_] := 
If[w==0 && h==2,1, (* stopping condition *)
If[w>0, (w/(w+h))*Rn[w-1,h+1],0] +(* draw whole *)
If[h>0,  (h/(w+h))*Rn[w,h-1],0]         (* draw half *)
]

R[w_,h_] := 
If[w==0 && h==2, 1,
If[w>0, HoldForm[Evaluate[w/(w+h)]]*R[w-1,h+1],0]+
If[h>0,  HoldForm[Evaluate[h/(w+h)]]*R[w,h-1],0]        
]

Here are some calculations for small intial numbers of  whole pills in the bottle (no initial half pills):

H=0;Do[W=i; Print["(",i," whole pills)\r",R[W,H]," = ",Style[Rn[W,H],FontWeight->"Bold"],"\r"],{i,2,5}]

And here is the answer  to the problem:

W=10;H=0; Rn[W,H]

Since the initial and final states are unique, it is also possible to walk the tree in the opposite direction, from final to initial state. The same operations are performed, only now in a different order.

Rrn[w_,h_] := 
If[w==W && h==H,1, (* stopping condition *)
If[w<W &&h>0, ((w+1)/(w+h))*Rrn[w+1,h-1],0] +(* undraw whole  *)
If[h< H+W-w,  ((h+1)/(w+h+1))*Rrn[w,h+1],0]     (* undraw half *)
] 

Rr[w_,h_] :=
If[w==W && h==H,1,
If[w<W &&h>0, HoldForm[Evaluate[(w+1)/(w+h)]]*Rr[w+1,h-1],0] +
If[h< H+W-w,  HoldForm[Evaluate[(h+1)/(w+h+1)]]*Rr[w,h+1],0]      
] 

H=0;Do[W=i; Print["(",i," whole pills)\r",Rr[0,2]," = ",Style[Rrn[0,2],FontWeight->"Bold"],"\r"],{i,2,5}]

W=10;H=0;Rrn[0,2]