Description
Consider the following game: You have a collection of coins of weighted coins of m different types.
Specifically, coins of category i come up heads with probability pi
, and you have ki of them. Therefore
the total number of coins C =
Pm
i=1 ki
. You also have an urn, which is initially empty. The coins
are in a pile outside the urn.
You now do the following. If either the urn or the outside is empty, pick a coin at random. If neither
the urn nor the outside is empty, then pick either the urn or the outside with probability 1/2, and
then pick a coin at random from the place that you have chosen. Flip the coin. If it comes up heads,
then put it in the urn; if it comes up tails then put it outside. Keep doing this forever.
This is a Markov process. The state of the system is determined by the number of coins of each
category in the urn. Since there can be between 0 and ki coins of category i in the urn, the total
number of states is q = (1 + k1) · (1 + k2) · . . .(1 + km)
For example, suppose that there is 1 coin of category 1, which is a fair coin, and 2 coins of category
2, which have a 0.8 chance of coming up heads. Then there are 6 states:
State number 1 2 3 4 5 6
# of type 1 in urn 0 0 0 1 1 1
# of type 2 in urn 0 1 2 0 1 2
The probability of a transition from state 2 to state 3 (for example) is calculated as follows: To
go from 2 to 3, you must pick “outside” (probability 1/2); then out of the two coins outside, pick
the one of type 2 (probability 1/2); then flip heads (probability 4/5)); so an overall probability of
(1/2) · (1/2) · (4/5) = 1/5. Computing the other probabilities in a similar way, we end up with the
transition matrix shown below and illustrated in the figure.
The transition matrix is:
T =
0.3 0.1 0 0.25 0 0
0.533 0.575 0.1 0 0.125 0
0 0.2 0.65 0 0 0.167
0.167 0 0 0.35 0.05 0
0. 0.125 0 0.4 0.425 0.133
0 0 0.25 0 0.4 0.7
1
5
0.4
0.42
0.05
0.35
2 3
0.2
0.1
0.65
0.7
6
1
4
0.3 0.57
0.17 0.25 0.13 0.13
0.4
0.13
0.25 0.17
0.53
0.1
Write the following functions:
• States(K) takes a vector K of the number of coins in each category, and returns an m×q array
S where S[I,J] is the number of coins of type I in the urn in state J. In the above example,
the call States([1,2]) should return the array
0 0 0 1 1 1
0 1 2 0 1 2
• Transition(S,H) takes as argument a state array S as output by States and a vector H,
where H[I] is the probability that coins of type I come up heads. It returns the associated
transition matrix between the states. In this example, the call Transition([0,0,0,1,1,1;
0,1,2,0,1,2], [0.5, 0.8]) should return the above transition matrix.
• Stationary(T) computes the stationary distribution for matrix T. This can be computed as
described in section 10.1.1.
• ProbFullUrn(T,N) takes as argument the matrix T and a number N and returns a vector P(I)
of size N of the probabilities that the urn will become full on or before the Ith flip, for I =
1:N. This is easily computed as follows: Modify the transition matrix T so that the final state
(where all the coins are in the urn) can transition only to itself; call this new transition matrix
U. Let S0, the initial probability distribution, be the column vector [1;0; …0], since initially
all the coins are outside. Then P[I] = (U
I
· S0)[Q]). (Q here is q, the number of states).
In the above example ProbFullUrn(T,6) should return [0,0,0.08, 0.184, 0.2888, 0.3859]
• ExpTimeToFill(T,EPS) returns the expected number of flips needed to fill the urn, to accuracy
approximately EPS. For any I, note that the probability that it takes I steps to fill the urn is
equal to (the probability that the urn is full on the Ith step) minus (the probability that it is
full on the I − 1st step). Compute the running sum of the product I times (the probability
that the urn becomes full on the Ith step) until (1−(the probability that the urn is full on the
Ith step) times I is less than EPS; then return the running sum.
For the above transition matrix you get
ExpTimeToFill(T,0.1) = 9.5418
ExpTimeToFill(T,0.01) = 9.6371
ExpTimeToFill(T,0.001) = 9.6468
2
