$\newcommand{\T}{\operatorname{TwoTails}}$
Algorithm $\T(k)$:
// all coin flips made are mutually independent
flip a fair coin twice;
if the coin came up heads exactly twice
then return $2^k$
else $\T(k + 1)$
endifYou run algorithm $\T(1)$, i.e., with $k = 1$. Define the random variable $X$ to be the value of the output of this algorithm. Let $m ≥ 1$ be an integer. What is $\Pr(X = 2^m)$?
Answer: $(3/4)^{m-1} · 1/4$
I don't understand how to arrive at this answer. I know that the probability of returning $2^k$ is $1/4$, then the recursive call has probability $3/4$. Is $m$ an arbitrary number, lets say, $3$? How would this look for $m = 3$?
Here is what it looks like when $m=3$: $$ \text{Tails}(1)\stackrel{\text{not TT}}{\longrightarrow}\text{Tails}(2)\stackrel{\text{not TT}}{\longrightarrow}\text{Tails}(3)\stackrel{\text{TT}}{\longrightarrow}\text{Output }2^3 $$ The probability of this happening is $$P(\text{not TT})\cdot P(\text{not TT})\cdot P(\text{TT})=(3/4)(3/4)(1/4)=(3/4)^{m-1}(1/4).$$