$3$ Expected Runtime of a Randomized Algorithm

Some algorithms need access to random numbers, and often different random choices made by the algorithm

can lead to different runtimes. In such a scenario, speaking about the algorithm's runtime doesn't make

sense as different executions of the same algorithm can have different runtimes. To fix this issue, we speak

instead about the expected running time, which is defined as follows for a randomized algorithm $A$ :

${\displaystyle \underset{t=0}{\overset{}{}}}t*Prob[A$ terminates $in$ time $t].$

In this exercise, you will compute the expected runtime for the following silly "bottles of beer" algorithm.

Input: An integer $n$

Initialize the "bottles of beer" variable BoB $=n.$

While BoB$>0$ :

flip an unfair coin where Prob$[$heads$]=\frac{2}{3},$ Prob$[$tails$]=\frac{1}{3}$;

if heads: BoB$=$BoB$-\frac{1}{\frac{?}{?}}$ "take one down, pass it around"

if tails: BoB$=$BoB$+\frac{1}{\frac{?}{?}}$ "restock the shelf"

Let $T_n$ denote the expected running time of this algorithm on input $n.$ Solve for $T_n.$