Question: 2015 Fall Final - 24
$\newcommand{\Heads}{{\rm H \scriptsize EADS}}$
Consider a coin that comes up heads with probability 1/3 and, thus, tails with probability 2/3.
Consider the following recursive algorithm $\Heads$, which takes as input a positive integer $k$:
$\mathbf{Algorithm}\ \Heads(k)\mathrm{:}$
$\text{flip the coin};$
$\mathbf{if}\ \text{the coin came up heads}$
$\mathbf{then}\ \mathrm{return}\ k + 1$
$\mathbf{else}\ \Heads(k + 1)$
$\mathbf{endif}$
You run algorithm $\Heads(1)$, i.e., with $k = 1$. Define the random variable $X$ to be the value of
the output of this algorithm. Let $m \geq 1$ be an integer. What is $\Pr(X = m + 1)$?
| $//$ | $\text{all coin flips made}$ $\text{are mutually independent}$ |
$\mathbf{if}\ \text{the coin came up heads}$
$\mathbf{then}\ \mathrm{return}\ k + 1$
$\mathbf{else}\ \Heads(k + 1)$
$\mathbf{endif}$
(a)
$(2/3)^{m}$
(b)
$(2/3)^{m+1}$
(c)
$2^{m}/3^{m+1}$
(d)
$2^{m-1}/3^{m}$