UC SCI 111, vM+.
Notebook 10

Markov chains

Introduction.

We are going to simulate the game mentioned in the first exercise. Two players A(be) and B(ert) throw coins. When heads turn up Abe pays Bert a dollar,when tails turn up Bert pays Abe a dollar. Before they begin Abe owns (Subscript[$s, A]) and Bert owns (Subscript[$s, B]). The game ends when one of the players runs out of money.
For our simulation one very important Mathematica function is the Random function.

throwcoin::usage = 
      "throwcoin throws the coin. You can set the initial capital by \
setting sa and sb. The variable p sets the fairness of the coin. The outcome \
is always \"Heads\" or \"Tail\".";

throwcoin[p_] := If[Random[] < p, "Heads", "Tail"];

The throwcoin expression plays the game. For instance:

Do[Print[throwcoin[ .5]], {i, 1, 5}];

Example: a ball game.

We give one example of how to do experiments with a Markov chain. This example mainly serves to help you with programming. The problem we consider is a variant of the occupancy problem. We have n urns. In each trial we place one ball in one of the urns. The process ends when one urn contains k balls. This is already quite a complicated process. We would like to have some idea of how long it lasts.

We start to define n and k.

\(n = 10; 
k = 7; \)

When the game starts the length of the game is zero and all the urns are empty.

urns = Table[0, {i, 1, n}]gamelength = 0;

The main loop of the process goes as follows

\(\(While[Max[urns] < k, 
\ \ val = n*Random[]; 
\ \ i = Ceiling[val]; 
      
\ \ urns[\([i]\)] = urns[\([i]\)] + 1; 
\ \ 
      gamelength = gamelength + 1
]; \)\)

What happens here is that we use a While loop. The While loop was also treated in notebook 2. The While loop

	 While[test,
		statement1;
		statement2
	 ] 

executes the statements until test becomes True.

The test is Max[urns]<k. This tests whether in the list urns (that initially just contained zeroes) all numbers are smaller then k. For instance

Max[{0, 5, 6, 8}] < 7

returns False.

The statements that are executed in the body of the While loop represent one trial. In each trial we take a random number between 0 and 1, and multiply this number by n. We obtain val. The probability that val lies between i and i-1 is 1/n. So we put the ball in the (i^( th)) urn if  the smallest integer larger than val equals i, that is:

	i=Ceiling[val];
	urns[[i]]=urns[[i]]+1;
	
Finally, we must not forget to increment our trial count

	gamelength=gamelength+1
	
Putting it all together in a Module, we get

\(\(playthegame[n_, k_] := 
      Module[{urns, gamelength, val, i}, 
\ \ \ \ \ gamelength = 0; 
		
        urns = Table[0, {i, 1, n}]; 
		
        While[Max[urns] < k, 
\ \ \ \ \ \ \ \ val = n*Random[]; 

          \ \ \ \ \ \ \ \ i = Ceiling[val]; 
\ \ \ \ \ \ \ \ 
          urns[\([i]\)] = urns[\([i]\)] + 1; 
\ \ \ \ \ \ \ 
          gamelength = gamelength + 1
\ \ \ ]; 
\ \ \ Return[gamelength]]
        		\)\)

We are ready to do a hundred experiments with for instance n=3, k=7.

Table[playthegame[3, 7], {i, 1, 100}]

Simulating the coin game.

In the following exercise we assume that(Subscript[s, A])+(Subscript[s, B])=3 and that the coin is fair.

Exercise 2.
a) Write a function whowins[sa_,sb_,p_] according to the following specification.

whowins::usage = "whowins[sa,sb,p] returns 1 if Abe wins the game \
and 0 if Bert wins the game. The assets of players Abe and Bert are \
respectively sa and sb. p measures the fairness of the coin, it is the \
probability that heads turn up.";

b) Check your answer on Exercise 1. (vi) by playing the (right version of) the game 10, 100, 1000 times and analysing the outcomes.
c) Change your whowins program in a howlong program:

howlong::usage = "howlong[sa,sb,p] returns the number of times the \
coin was tossed before the game ends. The assets of players Abe and Bert are \
respectively sa and sb. p measures the fairness of the coin, it is the \
probability that heads turn up.";

c) Again play the game 1000 times and produce a histogram of the gamelengths.
d) What is the chance that the game is finished in 1 round? And in exactly 2 rounds? And in exactly n rounds?
e) What is the expected number of rounds?
Hint: use Sum.

The formula for success.

Now assume that (Subscript[s, A])  +  (Subscript[s, B ]) = 
      10. 
\(The\ coin\ is\ still\ fair . \ 
        We\ are\ again\ interested\ in\ the\ winning\ chances\ of\ \(\(Abe\)\(.\)\)\)

Exercise 3.
a) Play the game 100 times for every possible asset Abe can start with.
Hint: playing the game once could look like this:

	s=10;
	experiment1=Table[whowins[i,s-i,.5],{i,1,s}];

b) Produce a barchart of the outcomes.

Now we move over to general s. But the coin is still fair.

Exercise 4.
a) Prove that the probability that Abe wins when starting with i dollars equals

	(i/s)
	
a) Point out the symmetry in this formula .