Additional homework 3 problem, not from book.



A. Let X be the number of tossess of a fair coin needed to observe two
consecutive heads. Determine a closed form expression for the expected
value of X. Simplify as much as possible (the final answer has a very 
simple form).

HINT: Recall from last week that the pmf of X is p(x) = FIB(x-1)/(2^x), 
x=2,3,..., where FIB(k) is the kth term of the Fibonacci sequence. You 
may assume this formula.

Denote a=(1+sqrt(5))/2 and b=(1-sqrt(5))/2. It can be shown that FIB(k) 
= (a^k - b^k)/sqrt(5). Here, sqrt(5) denotes the positive square root of 
five. You do not need to prove this result.

Optional, no extra credit: To check your result, write a computer
program to simulate X. Compute the average of X over a very large
number, say 10000, of repititions of this experiment.