Discrete Math HW. Needed ASAP
BryanAdams
ps_10.pdf
. MATH 366 - Problem Set 10 Due Thursday March 19, 2015
1. Let G be the graph shown below, which is the cycle graph C7 with an added chord. Consider a random walk on G in which the probability pij of moving from vertex i to vertex j is given by
pij = 1
di
where di is the degree of vertex i.
(a) Give the transition matrix P for this random walk.
(b) Give the 2-step transition matrix P 2.
(c) What is the probability of being in state 6 after 2 steps, if we start in state 6?
(d) What is the smallest value of n for which all entries of P n are positive? How would you interpret the significance of this value for n?
(e) For increasingly large values of n, at approximately what value of n do all rows of the matrix P n first appear equal (to three decimal places)? What is the significance of this, and what are the individual probabilities of being in each state?
2. Consider the transition matrix
P =
0 1 4
0 1 4
1 2
0 0 0 1 4
0 1 4
0 0 1 2
0 0 0 1
4 0 1
4 0 0 1
2 0
1 4
0 1 4
0 0 0 0 1 2
1 4
0 0 0 0 3 9
0 3 8
0 1 4
0 0 3 8
0 3 8
0 0 0 1
4 0 0 3
8 0 3
8 0 0 0 1
4 3 8
0 3 8
0
(a) Draw a planar graph consistent with P , including bidirectional edges with transition probabilities shown as edge weights.
(b) What three-dimensional geometric figure could this graph correspond to?
(c) Now make the edges one-way only by allowing the move i → j if and only if i < j. Propose a method to readjust the transition probabilities to reflect this change, such that we maintain consistency with the rule that “all choices leading out of a given state must have a total probability of 1” (which is equivalent to requiring that each row of P sums to 1). The resulting matrix should be “upper triangular”, such that all entries below the diagonal are zero.
(d) Redraw both the graph and the matrix P using your proposed method.
