这个作业是完成矩阵、马尔可夫链等随机过程相关的数学问题
Math 171 Homework Set 3
问题
1.假设状态空间为{1,2,3,4,5,6}，转移矩阵为
P =
1 2 3 4 5 6
1 0 1 0 0 0 0
2 0.4 0.6 0 0 0 0
3 0.3 0 0.4 0.2 0.1 0
4 0 0 0 0.3 0.7 0
5 0 0 0 0.5 0 0.5
6 0 0 0 0.3 0 0.7
确定此链是否不可约。另外，找到该链的所有经常性封闭类。
2.找到过渡矩阵的所有平稳分布
P =
1/2 0 0 0 1/2
0 1/2 0 1/2 0
0 0 1 0 0
0 1/4 1/4 1/4 1/4
1/2 0 0 0 1/2
3.（Ehrenfest的连锁店）假设我们有两个盒子，里面总共有N个球。在马尔可夫链的每一步，
一个球被随机均匀地选择，并从其当前框移到另一个。令Xn为
在时间n，第一个框中的球数。那么定义马尔可夫链的转移矩阵为
p（x，y）=
−
ñ
，如果y = x + 1;
X
ñ
如果y = x − 1;
0，否则。
证明该链的唯一平稳分布π是参数N和
1/2，即
π（x）=
ñ
X
</ s> </ s> </ s>
1个
2N
，对于x = 0，1，。 。 。 ，N.
4. (Graph random walk) Let G = (V, E) be a finite simple graph with a set of vertices V and a set of (undirected)
edges E. Let A = {a(x, y)}x,y∈S be the adjacency matrix of G, that is,
a(x, y) = (
1, if there is an edge in the graph between the vertices x and y;
0, if there is no such edge.
The degree deg(x) of a vertex x is the number of edges connected to the vertex. So deg(x) = P
y∈V
a(x, y).
The simple random walk on the graph G is the Markov chain with the state space S = V and transition matrix
P, given by
p(x, y) = a(x, y)
deg(x)
Show that π(x) = c deg(x) is a stationary distribution for a suitable choice of constant c, and determine the
value of c.
5. (Knight moves) Consider a standard 8 × 8 chess board. Let V be the set of vertices representing the squares
on the board (so V has 64 elements). Any two vertices x, y ∈ V are connected by an (undirected) edge if
and only if a knight can move from x to y. (The knight chess piece moves in an L-shape, i.e., two squares
horizontally and one square vertically, or two squares vertically and one square horizontally.[1]) Consider the
random walk on this graph. This Markov chain then represents a knight randomly moving around a chess
board. For every square x on the chessboard, compute the expected time of return Ex[Tx] to that square. (It
might be convenient to just draw the expected values on the chessboard itself.)