FOR j = 0 to N
j++;
FOR i = 0 to BIGNUM
i++;
where BIGNUM is chosen large enough that it takes you computer 1 second to
do this. Note: computers today are so fast you may have to use a double loop
to achieve delays this long with overflowing the constant integer data type.
Below is a historgram of the reported amount of time (in seconds) to compute the addition of 70764+34957 = 105721
61: x 35: xx 31: x 30: x 25: xx 22: x 20: xx 16: x 15: xxxxxxxxx 14: x 11: x 10: xxxxx 9: x 7: xxx 6: x33 students got the correct answer; one answered 105421 (transcription error).
The states of your Markov chain will be H and T, representing the fact that the current toss is heads or tails, respectively. The four transition probabilities are P(H|H), P(T|H), coming out of H and going to H and T, respectively; plus P(H|T), P(T|T), coming out of T and going to H and T, respectively.
These are computed as follows:
P(H|H) = #(HH) / [ #(HH) + #(HT) ]Thus, P(H|H)+P(T|H)=1 and P(H|T)+P(T|T)=1.
P(T|H) = #(HT) / [ #(HH) + #(HT) ]
P(H|T) = #(TH) / [ #(TH) + #(TT) ]
P(T|T) = #(TT) / [ #(TH) + #(TT) ]
For example, consider the following data set of 31 tosses:
H H H T T H T H T H H T H T H H T H T T H | H H T H T H T H T H
The first transition is HH, the second HH, the third HT, ..., the twentieith TH.
Counting up, the number of HH tranisitions in the first twenty is #(HH) = 4.
Counting up, the number of HT tranisitions in the first twenty is #(HT) = 7.
Counting up, the number of TH tranisitions in the first twenty is #(TH) = 7.
Counting up, the number of TT tranisitions in the first twenty is #(TT) = 2.
This would lead to the model:
4/11 7/11
|------ H -------> T-----|
|_______^ <------- ^_____|
7/9 2/9
Note: these may be computed by hand. You do not to write a program to compute these!
A program simulating ten tosses using this Markov chain would start in state H (because H is the 21st toss in THIS data set) and proceed as follows:
Initially: state:=H. FOR i= 1 to 10 Choose a random number r between 0 and 1.Compare the output to the last ten tosses above (tosses 22 through 31).
IF state is H, IF r is less than 4//11, output H and set state:=H. ELSE output T and set state:=T. IF state is T, IF r is less than 7/9, output H and set state:=H. ELSE output T and set state:=T.
Note: The program above will often not result in the best predictor. Instead, a "one shot" predictor for each toss should provide better results. Such a program would have access to the actual toss after it makes it guess. You could enter each toss after each guess or just test your program using the following pseudo-code:
tosses21to32=[H H H T H T H T H T H] Initially: state:=tosses21to32[0] FOR i= 1 to 10 Choose a random number r between 0 and 1.Again, compare the output to the last ten tosses above (tosses 22 through 31). In this case, you could have the program also track its performance (not required).
IF state is H, IF r is less than 4/11, output H as a guess ELSE output T as a guess IF state is T, IF r is less than 7/9, output H as a guess ELSE output T as a guess state:=tosses21to32[i]
Hint: for the above programs, you need a function that picks/returns a random number between 0 and 1. Matlab (available from the software library) and Perl have rand functions that return random numbers between 0 and 1; Java's Math.random() does the same thing. Other programming languages might have commands/classes that produce a random integer, R, from 1 to some integer LARGE. You can convert this by setting r=R/LARGE. For C++ users, Adams, Leestma, and Nyhoff, C++: An Introduction to Computing, 2nd Ed. discusses random number generation and the RandomInt class on pages 253-4. Python has a random module.