Solution: 2017 Winter Final - 22

Author: Michiel Smid

Question

Consider the following recursive algorithm $\TwoTails$, which takes as input a positive integer $k$:

$\mathbf{Algorithm}\ \TwoTails(k)\mathrm{:}$

$//$	$\text{all coin flips made are mutually}$ $\text{independent}$

$\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 $m \geq 1$ be an integer. What is $\Pr(X = 2^m)$?

(a)

$(3/4)^{m} \cdot 1/4$

(b)

$(1/4)^{m-1} \cdot 3/4$

(c)

$(1/4)^{m} \cdot 3/4$

(d)

$(3/4)^{m-1} \cdot 1/4$

Solution

Idk, I’ll just write down what I see and try to find a pattern

We have a 1 in 4 chance of landing 2 heads per double coin flip

$ Pr(X = 1) + Pr(X = 2) + Pr(X = 3) + Pr(X = 4) + … $

$ \frac{1}{4} + ( \frac{3}{4})( \frac{1}{4}) + {( \frac{3}{4})}^2 ( \frac{1}{4}) + … $

From this, I got the formula $ {( \frac{3}{4})}^{m-1} \cdot \frac{1}{4} $