Markov Chains and Monte Carlo Methods 06日目

Ioana A. Cosma and Ludger Evers, Markov Chains and Monte Carlo Methods
http://users.aims.ac.za/~ioana/notes.pdf
CC-by-nc-sa 2.5
http://creativecommons.org/licenses/by-nc-sa/2.5/za/legalcode

assignment 1

Q and A

2.

答案.

(a) 数学的帰納法を使う.$m=1$で確かに成立.
m=mで成立を仮定し,$m=m+1$での成立を示すのは$K^{(m+1)}=K^{m+1}=K K^{m}=K K^{(m)}$を使えばたやすい.
(b) stationary distributionを$\mu$とすると,$\mu^T K = \mu^T$が成り立つから,
$\mu^T(K-I) =0$を解く.
その解は$span\{(\beta, \alpha)^T\}$. $\mu$の要素は全て非負で和が1になることを考えれば,求めるdistibutionは$\mu = \frac{1}{\alpha + \beta}(\beta, \alpha)^T$.
(c) detailed-balanceを満たしていることを見れば良い.
$\mu_1 K_{1, 2} = \frac{1}{\alpha + \beta} \beta \alpha = \frac{1}{\alpha + \beta} \alpha \beta = \mu_2 K_{2,1}$だから,たしかに成立.

3.

(a, b) $\{\{1, 2, 3, 6, 7, 8 \}, \{ 4, 9\}, \{5\}, \{10\}\}$
それぞれ(recurrent, period=2), (transient, aperiodic), (transient, aperiodic), (transient, aperiodic)

4.

(a) 任意の$i < j$について,$P(X_{t+m_1}=j|X_i=i)>0, P(X_{t+m_2}=i|X_{t}=j)$を満たすような$m_1,m_2$が有ることを示せば良い. 定義より$P(X_{t+(j-i)}=j|X_t=i)=2^{-(j-i)}>0, P(X_{t+i}=i|X_{t}=j)=\underline{(1/2)}_{(1)}\cdot \underline{2^{-i}}_{(2)}>0$から示せた.
((1): $j$から$0$に遷移する確率, (2): $0$から$i$に遷移する確率)
(b) (i)recurrence

$S$が一つのcommunicating classだから,$0$がrecurrentであることを示せば十分である.
$k_{00}^{(t)} = 1/2 + 1/2 \cdot 1/2 + 1/2 \cdot (1/2 \cdot 1/2) + ... + 1/2 \cdot \underline{(1/2 \cdot ... \cdot 1/2)}_{t\text{個}} = 1-2^{-(1+t)}$であって,
$\lim_t k^{(t)}_{00}=1$ だから$\sum_t k_{00}^{(t)} \rightarrow \infty$すなわちrecurrent. 以上より示せた.

(ii) aperiodicity

$K_{ii}^{(m)} \begin{cases} = 0 \ \ \ (m < i) \\ \geq 2^{-(i+1)} \ \ (m \geq i) \end{cases}$から,$\{m \geq 1| K_{ii}^{(m)}>0\}= \{i, i+1, ...\}$.GCDは1であり,aperiodic. これが全ての$i$に成立する.

(c) transition matrixは
$$K = \left(\begin{array}{} 1/2 & 1/2 & 0 & 0 &\cdots \\ 1/2 & 0 & 1/2 & 0 &\cdots \\ 1/2 & 0 & 0 & 1/2 & \cdots \\ \vdots \end{array} \right)$$
である. stationaryな$\mu = (\mu_0 ,\mu_1, ...)^T$を計算する.
$\mu^T K = \mu^T$を解けばよい.
$\mu_0 = (\mu_0 + \mu_1 + \cdots) / 2$
$\mu_1 = \mu_0 /2$
$\mu_2 = \mu_1 / 2$
$\vdots$
であって,$\mu_i = \mu_{i-1}/2 \ \ ( i \geq 1)$ゆえに$\mu_i = \mu_0 \cdot 2^{-i}$.
$\sum_{i \geq 0} \mu_i = 2\mu_0 = 1$だから,$\mu_0=1/2$.以上より$\mu_i = 2^{-(i+1)}$.
stationary $\mu=(1/2, 1/4, 1/8, ...)^T$が示せた.

6.

(a) $$p(s|X_t = x_t) = \underline{(1- k_{x_tx_t})}_{(1)}\ \underline{(k_{x_tx_t})^{s-1}}_{(2)}$$
(1): $x_t$から他のstateに遷移する確率
(2): $s-1$回,$x_t$から$x_t$に遷移する確率
(b) $P(S_t > s_0 + s| S_t > s_0)=P(S_t>s)$を示す.
$lhs = P(S_t > s_0 + s, S_t > s_0)/P(S_t > s_0) = P(S_t > s_0 + s)/P(S_t > s_0)$
$$=\frac{1-\sum_{r=1}^{s_0+s}(1-k)k^{r-1}}{1-\sum_{r=1}^{s_0}(1-k)k^{r-1}}=k^{s_0+s}/k^{s_0}=k^s=1-P(s_t\leq s_0) = P(S_t > s)=rhs$$
よって示せた.

8.

def Wright_Fisher(a, b):
    path = [a]
    tn = a + b #2N
    xt = a
    for i in range(1000):
        xt = np.random.binomial(tn, xt/tn)
        path.append(xt)

    return path