1 .
$\newcommand{\TwoTails}{{\rm T {\scriptsize WO} T {\scriptsize AILS}}}$
Consider the following recursive algorithm $\TwoTails$, which takes as input a positive integer $k$:
$\mathbf{Algorithm}\ \TwoTails(k)\mathrm{:}$
$\text{flip a fair coin twice};$
$\mathbf{if}\ \text{the coin came up heads exactly twice}$
$\mathbf{then}\ \mathrm{return}\ 2^k$
$\mathbf{else}\ \TwoTails(k + 1)$
$\mathbf{endif}$
You run algorithm $\TwoTails(1)$, i.e., with $k = 1$. Define the random variable $X$ to be the value of the
output of this algorithm.
Let $k \geq 1$ be an integer. What is $\Pr(X = 2^k)$?
| $//$ | $\text{all coin flips made are mutually}$ $\text{independent}$ |
$\mathbf{if}\ \text{the coin came up heads exactly twice}$
$\mathbf{then}\ \mathrm{return}\ 2^k$
$\mathbf{else}\ \TwoTails(k + 1)$
$\mathbf{endif}$
(a)
$(3/4)^{k} \cdot 1/4$
(b)
$(1/4)^{k} \cdot 3/4$
(c)
$(3/4)^{k-1} \cdot 1/4$
(d)
$(1/4)^{k-1} \cdot 3/4$