求助一道马尔科夫链的习题

Ona4x4board,eachcellhasonemouseattime0.Eachsecond,themicewill
jumprandomlyintoaneighboringcell.Compute:
a)Theexpectednumberofemptycellsattime1.
b)Thestationarydistributionofnumberofemptycellsattimeinfinity.(Hint:usesimulation)
c)Theexpectednumberofemptycellsattimeinfinity(Youcanusesimulation).

不会，帮你加了空格，让别人看看吧。

On a 4x4 board,each cell has one mouse at time 0.Each second,the mice will jump randomly into a neighboring cell.Compute:
a)The expected number ofempty cells at time 1.
b)The stationary distribution of number of empty cells at time infinity. (Hint:use simulation)
c)The expected number of empty cells at time infinity(You can use simulation).

这题要好好做还是要花一点时间，我只做第一问，后面的你自己再加一点就好了。
先上第一问的答案
Let $X_{ij}$ be a Bernoulli random variable where
\begin{align*}
x_{ij} = \begin{cases} 1 \text{ if cell $(i,j)$ is empty at time 1}\\ 0 \text{ if cell $(i,j)$ is nonempty at time 1, }\end{cases}
\end{align*}
then we know that $E[X_{ij}] = p_{ij}$, where $p_{ij}$ is the probability that cell $(i,j)$ is empty at time 1.

There are 3 types of cells: Cell with 2 neighbors (corner cells: (0,0),(0,3),(3,0),(3,3))
\begin{align*}
p_{00} &= P(\text{mouse in cell (0,1) does not jump to (0,0)})\times P(\text{mouse in cell (1,0) does not jump to (0,0)})\\
&= \frac{2}{3}\times \frac{2}{3} = \frac{4}{9}.
\end{align*}
So by similar reasoning we have
\begin{align*}
p_{30}  = \frac{4}{9},\quad p_{03}  = \frac{4}{9},\quad p_{33}  = \frac{4}{9}.
\end{align*}
Cell with 3 neighbors (boarder cells: (0,1)(0,2),(1,0),(2,0),(3,1)(3,2),(1,3),(2,3))
\begin{align*}
p_{01} =& P(\text{mouse in cell (0,0) does not jump to (0,1)})\times P(\text{mouse in cell (1,1) does not jump to (0,1)})\\ &\times P(\text{mouse in cell (0,2) does not jump to (0,1)})\\
=& \frac{1}{2}\times \frac{3}{4}\times \frac{2}{3} = \frac{1}{4}.
\end{align*}
So by similar reasoning we have
\begin{align*}
p_{01}  = p_{02} = p_{10} = p_{20} = p_{31} = p_{31} = p_{13} = p_{23}  = \frac{1}{4}.
\end{align*}
Cell with 4 neighbors (boarder cells: (1,1)(1,2),(2,1),(2,2))
\begin{align*}
p_{01} =& P(\text{mouse in cell (0,1) does not jump to (1,1)})\times P(\text{mouse in cell (1,0) does not jump to (1,1)})\\ &\times P(\text{mouse in cell (1,2) does not jump to (1,1)})\times P(\text{mouse in cell (2,1) does not jump to (1,1)})\\
=& \frac{2}{3}\times \frac{2}{3}\times \frac{3}{4}\times \frac{3}{4} = \frac{1}{4}.
\end{align*}
So by similar reasoning we have
\begin{align*}
p_{11}  = p_{12} = p_{21} = p_{22} = \frac{1}{4}.
\end{align*}

Now, let $Y$ be the random variable of the number of empty cells at time 1, then we have
\begin{align*}
E[Y] = E\left[\sum\limits_{i=0}^3\sum\limits_{j=0}^3X_{ij}\right] = \sum\limits_{i=0}^3\sum\limits_{j=0}^3E[X_{ij}] = \sum\limits_{i=0}^3\sum\limits_{j=0}^3p_{ij} = \frac{43}{9} \approx 4.78.
\end{align*}

再给你贴一段验证第一问答案的代码

1. import random
   
2. 
   
3. possible_moves = [[-1, 0], [1, 0], [0, -1], [0, 1]]
   
4. 
   
5. 
   
6. def is_valid(i, j):
   
7.     return i >= 0 and i <= 3 and j >= 0 and j <= 3
   
8. 
   
9. 
   
10. def moves(i, j):
    
11.     res = []
    
12.     for k in possible_moves:
    
13.         s, t = k
    
14.         if is_valid(i + s, t + j):
    
15.             res.append([i + s, t + j])
    
16.     return res
    
17. 
    
18. 
    
19. def print_board(a):
    
20.     for i in range(len(a)):
    
21.         print
    
22.         for j in range(len(a[0])):
    
23.             print a[i][j],
    
24.     print
    
25.     print
    
26. 
    
27. 
    
28. def count_zeros(a):
    
29.     res = 0
    
30.     for i in range(len(a)):
    
31.         for j in range(len(a[0])):
    
32. 
    
33.             if a[i][j] == 0:
    
34.                 res += 1
    
35.     return res
    
36. 
    
37. 
    
38. total_zeros = 0
    
39. experiment = 10000
    
40. for k in range(experiment):
    
41.     a = [[1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1]]
    
42.     print_board(a)
    
43. 
    
44.     for i in range(4):
    
45.         for j in range(4):
    
46.             moves_set = moves(i, j)
    
47. 
    
48.             b = random.randint(0, len(moves_set) - 1)
    
49. 
    
50.             a[i][j] -= 1
    
51.             m_a, m_b = moves_set[b]
    
52.             a[m_a][m_b] += 1
    
53. 
    
54.     # print_board(a)
    
55.     # print count_zeros(a)
    
56.     total_zeros += count_zeros(a)
    
57. print total_zeros
    
58. print total_zeros / float(experiment)

复制代码

实验10000次得到的第一问的答案是4.7732.
第二三问都需要simulation了，在我贴的代码基础上再加改进就好。