Hint for hw06, expectation, continued
The average ("expected") number of rolls needed is the infinite sum:
1*(probability of 1 roll)
+ 2*(probability of 2 rolls)
+ 3*(probability of 3 rolls)
+ 4*(probability of 4 rolls)
+ ....
Let's write "P(R=3)" as shorthand for
"probability of exactly 3 rolls".
(In probability, we'd say that R is the random variable
for number-of-rolls.)
Computing
1*P(R=1) + 2*P(R=2) + 3*P(R=3) + 4*P(R=4) + ...
is a bit difficult:
if we didn't have the preceding factors of "2*, 3*, 4*",
then we'd have a geometric sum, and a formula from high school.
The hint is, we'll replace "2*P(R=2)" with
P(R=2)+P(R=2), and similarly
the 3*P(R=3) with the sum of itself 3 times.
This seems to make things messier, but the secret is to organize
all the summands in a nice way.
In particular, we'll array the summands as follows:
|
1*P(R=1) | + | 2*P(R=2) | + | 3*P(R=3) | + | 4*P(R=4) | + | ... |
| |
| = |
P(R=1) | + | P(R=2) | + | P(R=3) | + | P(R=4) | + | ... |
| |
| + | P(R=2) | + | P(R=3) | + | P(R=4) | + | ... |
| |
| | | + | P(R=3) | + | P(R=4) | + | ... |
| |
| | | | | + | P(R=4) | + | ... |
| |
| | | | | | | + | ... |
Our old phrasing could be thought of as trying to add each column,
and then add all those results, which is difficult.
Instead, try adding each row, and see if then you can add all those together!