Solution: 2015 Fall Final - 24

Author: Michiel Smid

Question

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{all coin flips made}$ $\text{are mutually independent}$

$\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)$?

(a)

$2^{m-1}/3^{m}$

(b)

$2^{m}/3^{m+1}$

(c)

$(2/3)^{m}$

(d)

$(2/3)^{m+1}$

Solution

$ Pr(X=2) = \frac{1}{3} $, m=1

$ Pr(X=3) = \frac{2}{3} \cdot \frac{1}{3} = \frac{2^1}{2^2} $, m=2

$ Pr(X=4) = \frac{2}{3} \cdot \frac{2}{3} \cdot \frac{1}{3} = \frac{2^2}{3^3} $, m=3

The pattern is that $ Pr(X=m) = \frac{2^{m-1}}{3^m} $