東京工業大学 工学院 情報通信系 2021年8月実施 午後 S1

标签：

• 东京科学大学
• 条件概率
• 期望与方差

Author

思齐塾, 祭音Myyura

Description

問題 S1

離散時刻 $t (t = 1, 2, \dots)$ において、 $S_t$ を 2 つの値 $\{1, 2\}$ のいずれかをとる 2 値の確率変数とする。 $S_1$ の確率分布 $P(S_1)$ と、 $S_t$ が与えられたときの $S_{t+1}$ の条件付き確率分布 $P(S_{t+1}|S_t)$ が、それぞれ次のように与えられているとする。

$$P(S_1 = 1) = P(S_1 = 2) = \frac{1}{2}, \quad P(S_{t+1} = j|S_t = i) = a_{i,j}, \quad \mathbf{A} = \begin{bmatrix} a_{1,1} & a_{1,2} \\ a_{2,1} & a_{2,2} \end{bmatrix} = \begin{bmatrix} 0.4 & 0.6 \\ 0.2 & 0.8 \end{bmatrix}$$

さらに、任意の時刻 $t$ において $P(S_{t+1}|S_1, S_2, \dots, S_t) = P(S_{t+1}|S_t)$ が成り立つとする。また、 $\mathbf{q}_t$ を $S_t$ の確率分布を表す列ベクトル $\mathbf{q}_t = [P(S_t = 1) \quad P(S_t = 2)]^T$ とする。このとき以下の各問いに答えよ。

なお、 $\mathbf{X}^T$ を行列またはベクトル $\mathbf{X}$ の転置、 $\mathbf{M}^{-1}$ を正則行列 $\mathbf{M}$ の逆行列、 $\mathbf{I}$ を単位行列とする。任意の正方行列 $\mathbf{M}$ に対して $\mathbf{M}^0 = \mathbf{I}$ と定義し、正整数 $N$ に対して $\mathbf{M}^N$ を行列 $\mathbf{M}$ と $\mathbf{M}^{N-1}$ の積 $\mathbf{M}\mathbf{M}^{N-1}$ とする。正方行列 $\mathbf{M}$ に対してあるスカラー $\lambda$ および零ベクトルでないベクトル $\mathbf{x}$ が存在して $\mathbf{M}\mathbf{x} = \lambda\mathbf{x}$ が成り立つとき、 $\mathbf{x}$ を $\mathbf{M}$ の固有ベクトルという。一般に $N$ 個の離散確率変数の同時確率分布 $P(X_1, X_2, \dots, X_N)$ について、 $P(X_1, X_2, \dots, X_N) = P(X_N|X_1, X_2, \dots, X_{N-1})P(X_1, X_2, \dots, X_{N-1})$ および $P(X_1, X_2, \dots, X_{N-1}) = \sum_{X_N} P(X_1, X_2, \dots, X_N)$ が成り立つ。ただし、 $\sum_X$ は確率変数 $X$ の取り得る全ての値について和をとることを表す。

---

1. $P(S_{t+1} = j) = \sum_{i=1}^2 P(S_{t+1} = j|S_t = i)P(S_t = i)$ より、 $\mathbf{q}_{t+1} = \mathbf{A}^T \mathbf{q}_t$ である。 $\mathbf{q}_2$ を求めよ。

2. $S_1$ の期待値 $E[S_1] = \sum_{s} sP(S_1 = s)$ を求めよ。ここでは $s$ は $S_1$ の取る値である。

3. a) $P(S_1 = 2, S_2 = 2, S_3 = 2)$ を求めよ。 b) $t = 1, 2, \dots, N$ において $S_t$ が全て 2 となる同時確率 $P(S_1 = 2, S_2 = 2, \dots, S_N = 2)$ を $N$ の関数として示せ。

4. $t$ が大きくなるとともに、 $\mathbf{q}_t$ はある列ベクトル $\mathbf{q}$ に近づく。 a) $t$ が十分に大きく $\mathbf{q}_t = \mathbf{q}$ であるとするとき、 $\mathbf{q}$ が行列 $\mathbf{A}^T$ の固有ベクトルであることを示せ。 b) $\mathbf{q}$ を求めよ。

5. 実数係数 $\gamma (0 < \gamma < 1)$ を考える。 $S_t$ に $\gamma^{t-1}$ を掛けた値 $\gamma^{t-1}S_t$ を考え、時刻 1 から $N$ までのその総和 $\sum_{t=1}^N \gamma^{t-1}S_t$ の期待値 $E[\sum_{t=1}^N \gamma^{t-1}S_t] = \sum_{t=1}^N \gamma^{t-1}E[S_t]$ を $U_N$ とする。 a) $S_t$ の期待値 $E[S_t]$ を $\mathbf{q}_t$ を用いて表せ。 b) $\mathbf{V}_N = \sum_{t=1}^N \gamma^{t-1}\mathbf{q}_t$ とする。このとき、 $(\mathbf{I} - \gamma \mathbf{A}^T)\mathbf{V}_N = (\mathbf{I} - f(\gamma)(\mathbf{A}^T)^N)\mathbf{q}_1$ が成り立つ。ここで $f(\gamma)$ は $\gamma$ の関数である。 $f(\gamma)$ を求めよ。 c) $N$ の関数として $U_N$ を求めよ。

题目描述

在离散时刻 $t=1,2,\ldots$，随机变量 $S_t$ 只取 $1,2$ 两个值。初始分布与一步条件分布为

$$P(S_1=1)=P(S_1=2)=\frac12,\qquad P(S_{t+1}=j\mid S_t=i)=a_{i,j},$$

其中转移矩阵

$$\mathbf A= \begin{bmatrix} a_{1,1}&a_{1,2}\\ a_{2,1}&a_{2,2} \end{bmatrix} = \begin{bmatrix} 0.4&0.6\\ 0.2&0.8 \end{bmatrix}.$$

并且对每个时刻 $t$ 都有马尔可夫性质

$$P(S_{t+1}\mid S_1,S_2,\ldots,S_t)=P(S_{t+1}\mid S_t).$$

以列向量

$$\mathbf q_t= \begin{bmatrix} P(S_t=1)&P(S_t=2) \end{bmatrix}^{T}$$

表示 $S_t$ 的分布。记 $\mathbf X^T$ 为矩阵或向量 $\mathbf X$ 的转置，$\mathbf M^{-1}$ 为可逆矩阵 $\mathbf M$ 的逆矩阵，$\mathbf I$ 为单位矩阵；对任意方阵定义 $\mathbf M^0=\mathbf I$，并对正整数 $N$ 递归定义 $\mathbf M^N=\mathbf M\mathbf M^{N-1}$。若存在标量 $\lambda$ 与非零向量 $\mathbf x$ 使 $\mathbf M\mathbf x=\lambda\mathbf x$，则称 $\mathbf x$ 为 $\mathbf M$ 的特征向量。另可使用联合分布的关系

$$P(X_1,\ldots,X_N) =P(X_N\mid X_1,\ldots,X_{N-1})P(X_1,\ldots,X_{N-1})$$

以及边缘化公式

$$P(X_1,\ldots,X_{N-1}) =\sum_{X_N}P(X_1,\ldots,X_N),$$

其中 $\sum_X$ 表示对随机变量 $X$ 的全部可能取值求和。回答以下各问。

1. 由

   $$P(S_{t+1}=j)=\sum_{i=1}^{2}P(S_{t+1}=j\mid S_t=i)P(S_t=i)$$

   可得 $\mathbf q_{t+1}=\mathbf A^T\mathbf q_t$。求 $\mathbf q_2$。

2. 按定义

   $$E[S_1]=\sum_s sP(S_1=s)$$

   求 $S_1$ 的期望，其中 $s$ 遍历 $S_1$ 的可能取值。

3. 求下列联合概率。

   a. $P(S_1=2,S_2=2,S_3=2)$。

   b. 用 $N$ 表示从 $t=1$ 到 $t=N$ 始终有 $S_t=2$ 的概率

   $$P(S_1=2,S_2=2,\ldots,S_N=2).$$

4. 当 $t$ 墣大时，$\mathbf q_t$ 趋近某个列向量 $\mathbf q$。

   a. 假定 $t$ 足够大时 $\mathbf q_t=\mathbf q$，证明 $\mathbf q$ 是 $\mathbf A^T$ 的特征向量。

   b. 求 $\mathbf q$。

5. 取实数 $\gamma$ 满足 $0<\gamma<1$。把 $S_t$ 乘以 $\gamma^{t-1}$，并记从时刻 $1$ 到 $N$ 的加权总和的期望为

   $$U_N =E\!\left[\sum_{t=1}^{N}\gamma^{t-1}S_t\right] =\sum_{t=1}^{N}\gamma^{t-1}E[S_t].$$

   a. 用 $\mathbf q_t$ 表示 $E[S_t]$。

   b. 定义

   $$\mathbf V_N=\sum_{t=1}^{N}\gamma^{t-1}\mathbf q_t.$$

   已知

   $$(\mathbf I-\gamma\mathbf A^T)\mathbf V_N =\bigl(\mathbf I-f(\gamma)(\mathbf A^T)^N\bigr)\mathbf q_1,$$

   求函数 $f(\gamma)$。

   c. 求 $U_N$ 关于 $N$ 的表达式。

Kai

問題の解答と詳細な解説

1. $\mathbf{q}_2$ の導出

与えられた初期分布 $\mathbf{q}_1$ と推移確率行列 $\mathbf{A}$ の転置 $\mathbf{A}^T$ を用いて $\mathbf{q}_2$ を計算します。 $\mathbf{q}_1$ は $S_1$ が 1 と 2 をとる確率が等しいことから、以下のようになります。

$$\mathbf{q}_1 = \begin{bmatrix} 0.5 \\ 0.5 \end{bmatrix}$$

また、$\mathbf{A}^T$ は以下のようになります。

$$\mathbf{A}^T = \begin{bmatrix} 0.4 & 0.2 \\ 0.6 & 0.8 \end{bmatrix}$$

関係式 $\mathbf{q}_{t+1} = \mathbf{A}^T \mathbf{q}_t$ に $t = 1$ を代入します。

$$\mathbf{q}_2 = \mathbf{A}^T \mathbf{q}_1 = \begin{bmatrix} 0.4 & 0.2 \\ 0.6 & 0.8 \end{bmatrix} \begin{bmatrix} 0.5 \\ 0.5 \end{bmatrix}$$

$$\mathbf{q}_2 = \begin{bmatrix} 0.4 \times 0.5 + 0.2 \times 0.5 \\ 0.6 \times 0.5 + 0.8 \times 0.5 \end{bmatrix} = \begin{bmatrix} 0.2 + 0.1 \\ 0.3 + 0.4 \end{bmatrix} = \begin{bmatrix} 0.3 \\ 0.7 \end{bmatrix}$$

よって、$\mathbf{q}_2 = \begin{bmatrix} 0.3 & 0.7 \end{bmatrix}^T$ です。

2. $E[S_1]$ の導出

期待値の定義 $E[S_1] = \sum_s s P(S_1 = s)$ に従って計算します。 $S_1$ の取り得る値 $s$ は 1 と 2 であり、それぞれの確率は 0.5 です。

$$E[S_1] = 1 \times P(S_1 = 1) + 2 \times P(S_1 = 2) = 1 \times 0.5 + 2 \times 0.5 = 0.5 + 1.0 = 1.5$$

よって、$E[S_1] = 1.5$ （または 3/2）です。

3. 同時確率の計算

a) $P(S_1 = 2, S_2 = 2, S_3 = 2)$ の導出

マルコフ性により、同時確率は条件付き確率の積に分解できます。

$$P(S_1 = 2, S_2 = 2, S_3 = 2) = P(S_3 = 2 | S_2 = 2) P(S_2 = 2 | S_1 = 2) P(S_1 = 2)$$

ここで、初期確率 $P(S_1 = 2) = 0.5$ であり、任意の時刻 $t$ について $P(S_{t+1} = 2 | S_t = 2) = a_{2,2} = 0.8$ です。これらを代入します。

$$P(S_1 = 2, S_2 = 2, S_3 = 2) = 0.5 \times 0.8 \times 0.8 = 0.32$$

よって、求める確率は 0.32 （または 8/25）です。

b) $P(S_1 = 2, S_2 = 2, \dots, S_N = 2)$ の導出

a) と同様に、$N$ 個の変数の同時確率を分解します。

$$P(S_1 = 2, \dots, S_N = 2) = P(S_1 = 2) \prod_{t=1}^{N-1} P(S_{t+1} = 2 | S_t = 2)$$

それぞれの確率を代入します。

$$P(S_1 = 2, \dots, S_N = 2) = 0.5 \times (0.8)^{N-1}$$

分数で表すと、以下のようになります。

$$P(S_1 = 2, \dots, S_N = 2) = \frac{1}{2} \left( \frac{4}{5} \right)^{N-1}$$

4. 定常分布 $\mathbf{q}$ の性質と導出

a) $\mathbf{q}$ が行列 $\mathbf{A}^T$ の固有ベクトルであることの証明

$t$ が十分に大きく、$\mathbf{q}_t$ が定常状態の列ベクトル $\mathbf{q}$ に収束したとします。このとき、次の時刻の確率分布 $\mathbf{q}_{t+1}$ も $\mathbf{q}$ に等しくなります。 関係式 $\mathbf{q}_{t+1} = \mathbf{A}^T \mathbf{q}_t$ に $\mathbf{q}_t = \mathbf{q}, \mathbf{q}_{t+1} = \mathbf{q}$ を代入すると、以下の式が成り立ちます。

$$\mathbf{q} = \mathbf{A}^T \mathbf{q}$$

これは、次のように書き換えられます。

$$\mathbf{A}^T \mathbf{q} = 1 \cdot \mathbf{q}$$

固有ベクトルの定義 $\mathbf{M}\mathbf{x} = \lambda\mathbf{x}$ と比較すると、$\mathbf{M} = \mathbf{A}^T, \mathbf{x} = \mathbf{q}, \lambda = 1$ に対応しています。 $\mathbf{q}$ は確率分布を表すベクトルであるため、要素の和が 1 であり、零ベクトルではありません。 したがって、$\mathbf{q}$ は行列 $\mathbf{A}^T$ の固有値 1 に対応する固有ベクトルであることが示されました。（証明終）

b) $\mathbf{q}$ の導出

$\mathbf{q} = \begin{bmatrix} q_1 & q_2 \end{bmatrix}^T$ とおきます。確率分布の性質から、要素の和は 1 です。

$$q_1 + q_2 = 1$$

また、a) の関係式 $\mathbf{A}^T \mathbf{q} = \mathbf{q}$ より、以下の連立方程式が得られます。

$$\begin{bmatrix} 0.4 & 0.2 \\ 0.6 & 0.8 \end{bmatrix} \begin{bmatrix} q_1 \\ q_2 \end{bmatrix} = \begin{bmatrix} q_1 \\ q_2 \end{bmatrix}$$

1行目の式を展開します。

$$0.4 q_1 + 0.2 q_2 = q_1$$

整理すると、$0.2 q_2 = 0.6 q_1$ となり、$q_2 = 3 q_1$ が得られます。 これを $q_1 + q_2 = 1$ に代入します。

$$q_1 + 3 q_1 = 1 \implies 4 q_1 = 1 \implies q_1 = \frac{1}{4}$$

$$q_2 = 1 - \frac{1}{4} = \frac{3}{4}$$

よって、$\mathbf{q} = \begin{bmatrix} 1/4 & 3/4 \end{bmatrix}^T$ です。

5. 割引和の期待値

a) $E[S_t]$ の $\mathbf{q}_t$ を用いた表現

$S_t$ は 1 と 2 の値をとるため、期待値は以下のように書けます。

$$E[S_t] = 1 \times P(S_t = 1) + 2 \times P(S_t = 2)$$

$\mathbf{q}_t = \begin{bmatrix} P(S_t = 1) & P(S_t = 2) \end{bmatrix}^T$ であるため、行ベクトル $\begin{bmatrix} 1 & 2 \end{bmatrix}$ と列ベクトル $\mathbf{q}_t$ の積として表現できます。

$$E[S_t] = \begin{bmatrix} 1 & 2 \end{bmatrix} \mathbf{q}_t$$

b) $f(\gamma)$ の導出

与えられた $\mathbf{V}_N$ の定義式は以下の通りです。

$$\mathbf{V}_N = \sum_{t=1}^N \gamma^{t-1} \mathbf{q}_t$$

関係式 $\mathbf{q}_t = (\mathbf{A}^T)^{t-1} \mathbf{q}_1$ を用いて代入します。

$$\mathbf{V}_N = \sum_{t=1}^N \gamma^{t-1} (\mathbf{A}^T)^{t-1} \mathbf{q}_1 = \sum_{t=1}^N (\gamma \mathbf{A}^T)^{t-1} \mathbf{q}_1$$

この式の両辺に左から $(\mathbf{I} - \gamma \mathbf{A}^T)$ を掛けます。等比数列の和（行列の多項式）の公式と同じ構造を展開します。

$$(\mathbf{I} - \gamma \mathbf{A}^T) \mathbf{V}_N = (\mathbf{I} - \gamma \mathbf{A}^T) \left( \mathbf{I} + \gamma \mathbf{A}^T + (\gamma \mathbf{A}^T)^2 + \dots + (\gamma \mathbf{A}^T)^{N-1} \right) \mathbf{q}_1$$

隣り合う項が相殺され、最初と最後の項だけが残ります。

$$(\mathbf{I} - \gamma \mathbf{A}^T) \mathbf{V}_N = (\mathbf{I} - (\gamma \mathbf{A}^T)^N) \mathbf{q}_1 = (\mathbf{I} - \gamma^N (\mathbf{A}^T)^N) \mathbf{q}_1$$

問題文で与えられた等式 $(\mathbf{I} - \gamma \mathbf{A}^T)\mathbf{V}_N = (\mathbf{I} - f(\gamma)(\mathbf{A}^T)^N)\mathbf{q}_1$ と比較すると、以下のようになります。

$$f(\gamma) = \gamma^N$$

c) $U_N$ の導出

$U_N = \sum_{t=1}^N \gamma^{t-1} E[S_t]$ です。a) の結果を代入します。

$$U_N = \sum_{t=1}^N \gamma^{t-1} \left( \begin{bmatrix} 1 & 2 \end{bmatrix} \mathbf{q}_t \right) = \begin{bmatrix} 1 & 2 \end{bmatrix} \sum_{t=1}^N \gamma^{t-1} \mathbf{q}_t = \begin{bmatrix} 1 & 2 \end{bmatrix} \mathbf{V}_N$$

$U_N$ を求めるためには、任意の時刻 $t$ における $\mathbf{q}_t$ の明示的な式が必要です。 行列 $\mathbf{A}^T$ の固有値 $\lambda$ を求めます。固有方程式 $|\mathbf{A}^T - \lambda \mathbf{I}| = 0$ を解きます。

$$\begin{vmatrix} 0.4 - \lambda & 0.2 \\ 0.6 & 0.8 - \lambda \end{vmatrix} = (0.4 - \lambda)(0.8 - \lambda) - 0.12 = \lambda^2 - 1.2\lambda + 0.32 - 0.12 = \lambda^2 - 1.2\lambda + 0.2 = 0$$

$(\lambda - 1)(\lambda - 0.2) = 0$ より、固有値は $\lambda_1 = 1, \lambda_2 = 0.2$ です。 $\lambda_1 = 1$ に対応する固有ベクトルは 4)b) で求めた $\mathbf{q} = \begin{bmatrix} 1/4 & 3/4 \end{bmatrix}^T$ です。 $\lambda_2 = 0.2$ に対応する固有ベクトルを $\mathbf{u}$ とおくと、$(\mathbf{A}^T - 0.2\mathbf{I})\mathbf{u} = 0$ より、

$$\begin{bmatrix} 0.2 & 0.2 \\ 0.6 & 0.6 \end{bmatrix} \mathbf{u} = \mathbf{0} \implies \mathbf{u} = \begin{bmatrix} 1 \\ -1 \end{bmatrix}$$

初期状態 $\mathbf{q}_1 = \begin{bmatrix} 1/2 & 1/2 \end{bmatrix}^T$ をこれらの固有ベクトルの線形結合で表します。

$$\begin{bmatrix} 1/2 \\ 1/2 \end{bmatrix} = c_1 \begin{bmatrix} 1/4 \\ 3/4 \end{bmatrix} + c_2 \begin{bmatrix} 1 \\ -1 \end{bmatrix}$$

これを解くと $c_1 = 1, c_2 = 1/4$ となります。よって、

$$\mathbf{q}_1 = \begin{bmatrix} 1/4 \\ 3/4 \end{bmatrix} + \frac{1}{4} \begin{bmatrix} 1 \\ -1 \end{bmatrix}$$

$\mathbf{q}_t = (\mathbf{A}^T)^{t-1} \mathbf{q}_1$ であるため、それぞれの固有値が $(t-1)$ 乗されます。

$$\mathbf{q}_t = 1^{t-1} \begin{bmatrix} 1/4 \\ 3/4 \end{bmatrix} + \frac{1}{4} (0.2)^{t-1} \begin{bmatrix} 1 \\ -1 \end{bmatrix} = \begin{bmatrix} 1/4 \\ 3/4 \end{bmatrix} + \frac{1}{4} (0.2)^{t-1} \begin{bmatrix} 1 \\ -1 \end{bmatrix}$$

これを用いて $E[S_t] = \begin{bmatrix} 1 & 2 \end{bmatrix}\mathbf{q}_t$ を計算します。

$$E[S_t] = \begin{bmatrix} 1 & 2 \end{bmatrix} \left( \begin{bmatrix} 1/4 \\ 3/4 \end{bmatrix} + \frac{1}{4} (0.2)^{t-1} \begin{bmatrix} 1 \\ -1 \end{bmatrix} \right) = \left( \frac{1}{4} + \frac{6}{4} \right) + \frac{1}{4}(0.2)^{t-1} (1 - 2)$$

$$E[S_t] = \frac{7}{4} - \frac{1}{4}(0.2)^{t-1}$$

これを $U_N$ の式に代入します。

$$U_N = \sum_{t=1}^N \gamma^{t-1} \left( \frac{7}{4} - \frac{1}{4}(0.2)^{t-1} \right) = \frac{7}{4} \sum_{t=1}^N \gamma^{t-1} - \frac{1}{4} \sum_{t=1}^N (0.2\gamma)^{t-1}$$

等比数列の和の公式 $\sum_{k=0}^{n-1} r^k = \frac{1 - r^n}{1 - r}$ を適用して整理します。

$$U_N = \frac{7(1 - \gamma^N)}{4(1 - \gamma)} - \frac{1 - (0.2\gamma)^N}{4(1 - 0.2\gamma)}$$