|
O-17
Post time 2023-8-25 05:05
如果把终止条件改成 "两个人比分差值大于等于 $n$ 时游戏结束" 可以把所有可能的状态列出来, 我们可以用有序的二元整数对来描述所有状态
$$
\Omega=\{(x,y):\left(x=1\wedge-n<y\leqslant n\right)\vee\left(x=2\wedge-n\leqslant y< n\right)\}\subset\mathbb{Z}^2
$$
其中 $x=1$ 表示下一次投球的人是甲, $x=2$ 则表示下一次投球的人是乙, $y$ 的值为此时甲的得分减去乙的得分 (每进一个球即得一分) .
易知 $|\Omega|=2n$ ,确定完所有可能的状态后, 根据题意不难写出如下的 Markov Chain.
\begin{matrix}
\color{red}{(1,n)}\\
\uparrow a\\
\color{blue}{(1,n-1)}&\underset{1-a}{\overset{1-b}{\leftrightarrows}}&\color{blue}{(2,n-1)}\\
\uparrow a&&\downarrow b\\
\color{blue}{(1,n-2)}&\underset{1-a}{\overset{1-b}{\leftrightarrows}}&\color{blue}{(2,n-2)}\\
\uparrow a&&\downarrow b\\
\cdots&\cdots&\cdots\\
\uparrow a&&\downarrow b\\
\color{blue}{(1,0)}&\underset{1-a}{\overset{1-b}{\leftrightarrows}}&\color{blue}{(2,0)}\\
\uparrow a&&\downarrow b\\
\cdots&\cdots&\cdots\\
\uparrow a&&\downarrow b\\
\color{blue}{(1,2-n)}&\underset{1-a}{\overset{1-b}{\leftrightarrows}}&\color{blue}{(2,2-n)}\\
\uparrow a&&\downarrow b\\
\color{blue}{(1,1-n)}&\underset{1-a}{\overset{1-b}{\leftrightarrows}}&\color{blue}{(2,1-n)}\\
&&\downarrow b\\
&&\color{red}{(2,-n)}\\
\end{matrix}
比如当 $n=2$ 时, 可以写出状态转移矩阵 $A$ 和初始向量 $v_0$ ,
$$A=
\begin{pmatrix}
0&0&a&0&0&0&0&0\\
0&0&0&0&0&0&0&b\\
0&0&0&1-b&a&0&0&0\\
0&0&1-a&0&0&0&0&0\\
0&0&0&0&0&1-b&a&0\\
0&0&0&b&1-a&0&0&0\\
0&0&0&0&0&0&0&1-b\\
0&0&0&0&0&b&1-a&0
\end{pmatrix},~v_0=
\begin{pmatrix}
0\\0\\0\\0\\0.5\\0.5\\0\\0
\end{pmatrix}\sim
\begin{Bmatrix}
(1,2)\\
(2,-2)\\
(1,1)\\
(2,1)\\
(1,0)\\
(2,0)\\
(1,-1)\\
(2,-1)
\end{Bmatrix}
$$
第 $n$ 次投篮后的状态向量 $v_n=A^nv_0$ , 其分量代表此时处于对应状态的概率. |
|