Re: A Probability Question
[ QUOTE ]
Could you explain how you got the initial difference equation?
[/ QUOTE ]
The initial difference equation comes from first step analysis. There are four disjoint events that could happen in the first steps: (1) the first flip is a tail, (2) the first two flips are HT, (3) the first three are HHT, and (4) the first three are HHH. These account for all possibilities and their probabilities are 1/2, 1/4, 1/8, and 1/8 respectively.
After event (1), you start over and your expectation is E_{n-1}. After event (2) it is E_{n-2}. After event (3), it is E_{n-3}. After event (4), however, you gain a point before starting over. So your expectation is 1 + E_{n-3}. Hence, your expectation at the start of the game is given by the first formula in my earlier post.
[ QUOTE ]
Also, how do you move from that to the characteristic function? Do you have to assume that the formula for E_n is polynomial.
[/ QUOTE ]
This technique is analogous to the technique used for solving homogeneous, linear differential equations with constant coefficients (there you look for solutions of the form e^{rt}).
With the difference equation, we are looking for solutions of the form r^n. Under this assumption, we are led to the characteristic equation. When this equation has distinct roots, it can be shown that the resulting solutions are linearly independent. Also, when the roots come in complex conjugate pairs, it can be shown that the two resulting solutions can be replaced by their real and imaginary parts, and still yield a full set of linear independent solutions.
The theorems for difference equations are so similar to those for differential equations (and so much easier to prove) that I would recommend, if you're interested, just reviewing the differential equation stuff and working out the difference equation stuff on your own. But if you really want a reference, I'm sure you can find a good one just by googling for it. If you can't, ask me again later and I'll see what I can dig up.
|