EE 381 Assignment 06 – Markov Chains solution

$25.00

Category:

Description

5/5 - (4 votes)

0. Introduction and Background Material
0.1. A simple example of a Markov chain
A machine can be in two possible states A and B. The state of the machine at time ( 1) k + is
determined by the state of the machine at the previous time step k :
• If the state at k is A, then the state at ( 1) k + will be A with probability 11 p
• If the state at k is A, then the state at ( 1) k + will be B with probability 12 p
• If the state at k is B, then the state at ( 1) k + will be A with probability 21 p
• If the state at k is B, then the state at ( 1) k + will be B with probability 22 p
These state transitions are shown schematically in Figure 1. Also, Figure 2 shows the same
information on state transition probabilities in a more compact form.

Figure 0.1 Figure 0.2
Clearly: 11 12 p p + =1 and 21 22 p p + =1.
A p11 p12
TIME k TIME (k+1)
B
A
B
p22
p21
A
B
p12
p21
p11
p22
EE 381 Project : Markov Chains Dr. Chassiakos – Page 2
For the current problem the transition probabilities have the following values:
11 12 21 22 pppp = 0.8 ; 0.2 ; 0.5 ; 0.5 = = =
The initial state is randomly distributed between state “A” and state “B”.
The probability of the initial state being “A” is given as: Prob (Initial State = A) = 0.4
The probability of the initial state being “B” is given as: Prob (Initial State = B) = 0.6
The graphs below show several simulation results for this two-state Markov chain. The chain is
run for n =15 time steps.
Figure 0.3 shows a single simulation run of the chain. The initial state of the chain is “A”. The
graph shows the evolution of the chain for the next 15 steps. In this particular simulation the
chain goes through the following sequence of states, after the initial state “A”:
[A BBABBAABBBAAABA]
Figure 0.4 shows another single simulation run of the chain. In this case the initial state of the
chain is “B”. The graph shows the evolution of the chain for the next 15 steps. In this particular
simulation the chain goes through the following sequence of states, after the initial state “B”:
[B AAABAAAAAAAAABA]
Figure 0.3 Figure 0.4
EE 381 Project : Markov Chains Dr. Chassiakos – Page 3
Figure 0.5 shows the combined results from N=10000 simulation runs of the chain. It is seen that
the chain starts at state “A” 40% of the time, and at state “B” 60% of the time. The graph shows
the evolution of the chain for the next 15 steps.
Figure 0.6 shows the results of the state evolution using the “State Transition Matrix” approach.
The probabilities are CALCULATED based on the transition matrix. The probabilities they ARE
NOT derived as the result of N=10000 simulation runs, as was done in Figure 0.5. It is noted that
the results of Figures 0.5 and 0.6 are very similar, almost identical, confirming the fact that the
state transition matrix approach can be used instead of a step-by-step simulation.
Figure 0.5 Figure 0.6
EE 381 Project : Markov Chains Dr. Chassiakos – Page 4
1. A three-state Markov Chain
Follow the previous code as a guide, and simulate the Markov chain defined in problem 11.1 of
the AMS text by Grinstead & Snell, p. 406 (reference [1]).
The transition probabilities are given by the following matrix:
111
333
1 1 0
2 2
111
442
P
 
 
 
  =  
 
     
1. The initial probability distribution of the state is given by: [ ] 111
424
RNS   =    
2. Run each experiment for n =15 time steps. In order to obtain meaningful statistical data
perform a total of N =10,000 experiments.
3. After your experimental simulations are completed, use the State Transition Matrix approach
and compare the results.
SUBMIT a report with the results and your code. You must follow the guidelines given in the
syllabus regarding the structure of the report. Points will be taken off, if you do not follow the
guidelines. The report should contain:
• One plot showing one single-simulation run for n =15 steps, similar to Figure 0.3, but for a
three-state chain. For an example see the figure below. Note that this figure does not have
labels, but your plot should have the appropriate labels and title.
• A plot with the experimental probabilities for the states R, N, S, similar to Figure 0.5
• A plot with the probabilities obtained through the state transition matrix approach for the
three states R, N, S, similar to Figure 0.6
• The code in an Appendix
• Make sure that all the plots are properly labeled
EE 381 Project : Markov Chains Dr. Chassiakos – Page 5
2. The Google PageRank Algorithm
This problem presents an introduction to the algorithm used for ranking web pages for searching
purposes. The algorithm was developed by Google’s founders Page and Brin with Motwani and
Winograd, and was first published in 1998 (see reference [2]). The PageRank algorithm allowed
Google to rise to the top of all web search engines within a matter of months after its
implementation, outperforming the established search engines of the time such as AltaVista and
Yahoo. The algorithm is based on the theory of Markov chains, utilizing the information on the
number of links leading to an existing webpage.
The current problem uses a simplified web in order to show how the algorithm works (see
reference [3]). The simplified web consists of 5 pages only, and it is shown schematically in
Figure 2.1.
Figure 2.1: A five-page web
A Markov chain model of an impartial surfer visiting web pages is created as following:
• At time k the surfer is on page X , where X ABCDE ∈{ ,,,, } .
• At time ( 1) k + the surfer will move randomly to another page Y , which must be linked to X .
• The state k S of the Markov chain at time k is defined as the page which the surfer is visiting
at time k : S ABCDE k ∈{ ,,,, } .
• To create the Markov chain model, the algorithm assumes that all pages that can be reached
from X have the same probability to be visited by the surfer. Thus:
( 1 )
1 , if can be reached from (Total number of links leaving page X)
Prob |
0 , if cannot be reached from
k k
Y X
S YS X
Y X
+


 = = = 



• For example: 1
1 Prob ( | ) 3 k k S AS C + = = = ; Prob ( | ) 0 k k 1 S ES D + = = = ; etc.
A
B
D
C
E
EE 381 Project : Markov Chains Dr. Chassiakos – Page 6
• Based on these probabilities the State Transition Matrix ( P ) of the Markov chain is
constructed. The left eigenvector w of P corresponding to the eigenvalue λ =1 (which is a
fixed vector of the Markov chain) is computed from: wP w=
• The PageRank algorithm uses the vector w to rank the pages of the five-page web in terms of
visiting importance.
To complete this problem follow the steps below:
1. Create the 5 5 × State Transition Matrix P with the values of the transition probabilities
2. Assume that initially all pages are equally likely to be visited, i.e. use the initial state
probability distribution vector: 1 [ ] 11111
55555
v ABCDE   = =    
3. Calculate the probability vectors for n =1,2, 20  steps, using the State Transition
matrix only. Note that you ARE NOT asked to run the complete simulation of the chain. You
are only asked to use the State Transition matrix approach to calculate the probability
vectors for n steps.
4. Rank the pages {ABCDE ,,,, } in order of importance based on the results from the previous
step
5. Create a plot of the calculated state probabilities for each of the five states {ABCDE ,,,, } vs.
the number of steps for n =1,2, 20  . This should be similar to the plot in Figure 0.6
6. Assume that the surfer always starts at his/her home page, which for the purposes of this
problem is page E . Repeat steps (2)-(5) with the new state probability distribution vector:
v ABCDE 2 = [ ] = [00001]
SUBMIT a report with the results and your code. You must follow the guidelines given in the
syllabus regarding the structure of the report. Points will be taken off, if you do not follow the
guidelines. The report should contain:
• The 5 5 × State Transition Matrix P
• For the initial state probability distribution vector 1 v :
 Submit the page ranking calculated in Step 4. Use Table 1 for your answer. Note: You will
need to replicate the table in your Word file, in order to provide the answer in your report.
Points will be taken off if you do not use the table.
 Submit the plot created in Step 5.
• For the initial state probability distribution vector 2 v
 Submit the page ranking calculated in Step 4. Use Table 1 for your answer. Note: You will
need to replicate the table in your Word file, in order to provide the answer in your report.
Points will be taken off if you do not use the table.
 Submit the plot created in Step 5.
• The code in an Appendix.
• Make sure the plots are properly labeled

EE 381 Project : Markov Chains Dr. Chassiakos – Page 7
Initial probability vector: 1 v Initial probability vector: 2 v
Rank Page Probability Rank Page Probability
1 1
2 2
3 3
4 4
5 5
Table 1.
References
[1] “Introduction to Probability”, C.M. Grinstead and J.L Snell, American Mathematical
Society, electronic version, 2003, 2nd edition
[2] L. Page, S. Brin, R. Motwani, and T. Winograd. “The PageRank Citation Ranking:
Bringing Order to the Web”, Technical Report, Stanford University, 1998.
[3] “Mathematics & Technology”, C. Rousseau & Y. Saint-Aubin, Springer, 2008.