Auto Generated Question

Back

1 . Consider the following recursive algorithm

T H R E E H E A D S O R T H R E E T A I L S

, which takes as input a positive integer

k

$Algorithm$ $T H R E E H E A D S O R T H R E E T A I L S (k)$ :
$flip a fair coin three times;$
$if the result is H H H or T T T$
$then return k$
$else$
$T H R E E H E A D S O R T H R E E T A I L S (k + 1)$
$endif$

You run algorithm

T H R E E H E A D S O R T H R E E T A I L S (1)

, i.e., with

k = 1

. Define the random variable

X

to be the value of the output of this algorithm. What is the expected value of

X

(a)

(b)

(c)

(d)