gjohnson@cornell.UUCP (Gregory Johnson) (01/27/84)
A (long) while back, I posed the following problem:
What are the odds of receiving various outcomes
after typing in
??? 6
More generally, what if I type in K '?'s and follow
them by the integer 'N'?
In English, say I spin a roulette wheel with N slots, and it comes
up x1. I then spin a roulette wheel with x1 slots, and it comes up
x2. I repeat the process k times. What is the probability
distribution for xk?
Here is a solution due to Don Bentley of Pomona College:
View the problem as a Markov chain with N states. State i (in 1 .. N) has
probability 1 / ( 1 + N - i ) of going to each of states i through N.
For you computer science types, imagine a non-deterministic finite
automaton with N states, and with arcs labeled by probabilities.
Each state i has transition arcs
to states i through N. All outgoing arcs from each node have
equal probability. As an example, if N is 4 then the probabilities
for going from states i to j are summarized in the following Markov
matrix:
to
/ \
1: 2: 3: 4:
1: 1/4 1/4 1/4 1/4
/ 2: 0 1/3 1/3 1/3
from 3: 0 0 1/2 1/2
\ 4: 0 0 0 1
The following (index-origin 1) function generates the matrix:
z := markov n
[1] z := (2 rho n) rho divide iota n
[2] z := reverse[ 1 ] transpose n
[3] z := (2 rho n) take ( 1 - iota n ) rotate n, (2 rho n) rho 0
One then takes the Markov matrix, and multiplies it by itself (using
the standard inner product) k times. The first row of the resulting
matrix gives the desired set of probabilities.
- Greg Johnson
cornell!gjohnson
gjohnson@cornell