Going Up Until You Go Down...With Surprises
Unless you are quite proficient with statistics and probability, solving these problems is not easy. But, one of the nice things about mathematics is that you can still model the three situations and develop an intuition regarding reasonable answers to the problems. And, the best part of all, is to eventually discover the surprising answers to the questions! 2, 3, 4, 4, 6, 6, 5
That is, a decrease in the rolled number did not occur until the sixth roll. Is this unusual? Try it mulitple times before continuing.
Suppose you roll a regular die...with these results:
Problem 1: What is the expected number of die rolls before a decrease occurs?
Problem 2: Given a n-sided die, what is the expected number of die rolls before a decrease occurs? (Again, pull out your D&D dice and gather some data first.)
Now, rather than rolling a die, suppose you are picking random numbers in the interval [0,1], which is a continuous distribution. Model this by having your calculator/computer produce sequences of "pseudo-random" numbers, such as: 0.1234, 0.3251, 0.3266, 0.7834, 0.9102, 0.3741
Problem 3: What is the expected number of random numbers before a decrease occurs?
Source: J. Siehler's "How Long Until a Random Sequence Deceases?" Math. Magazine, Dec, 2010, pp. 374-379.
Hint: First, develop an intuition for a reasonable answers by rolling a die or using a calculator to pick random numbers.
As to the mathematics, you need to determine a formula for the probability that a sequence of length r is nondecreasing.
Then, the probability that the first decrease is the r-th position is the difference between the probabilities of in being nondecreasing for r steps and for r-1 steps.
The final task is to to use this difference to produce an expected value....which is not trivial.
Solution Commentary: Hopefully, you have modeled the situations to intuit some reasonable responses. Compare your thoughts with these conclusions (see source for proofs):
- For n-sided die, probability that first decrease occurs on r-th roll is n+r-2Cr[(r-1)/nr]. Returning to the example with a regular die, the probability of the decrease occurring on the 7th roll is about 0.007.
- For n-sided die, expected number of rolls before a decrease occurs is [n/(n-1)]n. That is, for a regular die, the expected number of rolls is (6/5)6 or about 3.
- A surprise is to note that as the number n of sides increases, the expected value decreases. Thus, flipping a coin (H=1, T=2) is best, with an expected value of (2/1)2 or 4 flips.
- And the biggest surprise of all, for the case of picking random numbers in [0,1], the expected value is e. It seems to appear everywhere!