Sometimes the average is anything but average
A Well-Mannered Function
If you delve into the code for the factorial function and replace the multiplication sign with a plus sign, you wind up with a procedure for calculating triangular numbers—1, 3, 6, 10, 15, 21.... To see why they're called triangular, think of 10 bowling pins or 15 billiard balls. Whereas the factorial of 4 is 1x2x3x4=24, the corresponding triangular number is 1+2+3+4=10. (There is a well-known shortcut for computing the nth triangular number: n(n+1)/2. It's interesting that no comparable shortcut exists for factorials, although there are approximations.)
Having converted the n! code into a program for generating triangular numbers, we can clearly make the same change in the program for n?. The result will be a procedure that rolls an n-sided die and keeps a running sum (rather than a product) until a 1 turns up.
Sums of random variables are much better-behaved than products. With randomized triangular sums, the algorithm for calculating the arithmetic mean works flawlessly. Generate a sample of values (all for the same n), add them up, divide by the size of the sample, and you get an estimate of the mean. With a small sample, the estimate is somewhat unreliable, so that repeating the procedure is likely to produce a substantially different result. But as the sample size increases, the estimates grow more consistent. The illustration at right shows the convergence of sample means toward the true mean for 2,000 samples of various sizes.
» Post Comment