From One Billion to Zero
Calculator: TI-34 II.
Start with 1 billion, 1,000,000,000. Choose randomly a whole number n between 0 and one billion -1. Then choose again randomly a number between 0 and n -1. Repeat this process until you hit zero. How many steps did it take? Investigate the distribution of the number of steps of this process that lead from 1 billion to zero.
You may do it theoretically or experimentally. In any case, design and implement an efficient program for the TI-34 which allows you to simulate this process.
Notice that you always choose a number smaller than the current one. So the program on the TI-34 II and its execution may look as follows.
Define,
OP1=RANDI(0,Ans-1)
Enter, and see,
E9 = 1000000000.
Repeat,
OP1 486436969.
OP1 140535564.
OP1 3 51634128.
OP1 4 27448367.
.......................................................................
.......................................................................
OP1 13 6.
OP1 14 4.
OP1 15 3.
OP1 16 0.
Thus in this example it took 16 steps to go down from 1 billion to 0.
The question that we want to answer is, "What is the average number s of steps that it takes to go down from 1 billion to 0?"
We will look at a general formula for the average number of steps s(n) it takes to go down from n > 0 to 0. We will start not with 1 billion, but with 1.
| n = | s(n) = | Paths (with their probabilities in parentheses): | |
| 1 | 1 | 1,0 (1) | s(1) = 1*1 = 1 |
| 2 | 1 + 1/2 | 2,0 (1/2); 2,1,0 (1/2) | s(2) = 1/2*1 + 1/2*2 = 1/2 + 1 |
| 3 | 1 + 1/2 + 1/3 | 3,0 (1/3); 3,1,0 (1/3); 3,2,0 (1/6); 3,2,1,0 (1/6) | s(3) = 1/3*1 + 1/3*2 + 1/6*3 = 1 + 1/2 + 1/3 |
........................................................................................................................
Is it true that in general we have the following formula for s(n)?
s(n) = 1 + 1/2 + 1/3 + ... + 1/n
We already know that it is true for the first three values of n. In order to show that this pattern holds forever, we show that,
If this formula is true for n, namely,
s(n) = 1 + 1/2 + 1/3 + ... + 1/n ,
then it is also true for n+1, namely
s(n+1) = 1 + 1/2 + 1/3 + ... + 1/n + 1/n+1.
When we start at n+1, then with probability n/n+1 we skip n and choose with equal probability a number between 0 and n-1. In this case the average number of steps is s(n). (It is the same as if we had started at n.)
The second possibility is that we choose n in our first step. This has probability 1/n+1. And the average number of steps is 1 + s(n).
Thus the average number of steps when we start at n+1 is the combination of these two averages.
s(n+1) = n/n+1*s(n) + 1/n+1*(1 + s(n)) = s(n) + 1/n+1
So if s(n) = 1 + 1/2 + ... + 1/n, then s(n+1) = 1 + 1/2 + ... + 1/n + 1/n+1.
This exact formula is not good enough, because for large n we cannot practically compute such a long sum. But Euler found that for large n,
1 + 1/2 + ... + 1/n is almost equal to ln(n) + c,
where ln(n) is the natural logarithm of n and c ≈ .58.
With the TI-34 II we can check that,
ln(E9) + .58 ≈ 21.3
Therefore the average number of steps when we move from one billion to 0 is slightly bigger than 21.
Here are statistics from 10 trials with the TI-34 II:
22
26
25
16
16
19
21
21
22
27
average = 21.5
To get a sequence from one billion to zero on the TI-83, from the home screen, enter
0→B:E9→A
B+1→B:randInt(0,A-1) →A:{B,A}
Enter
Enter
...
Footnote. A book, Gamma, by Julian Havil (Princeton University Press, Princeton, NJ, 2003) explores Euler's constant, which is referred to above as "c".