東京大学 新領域創成科学研究科 メディカル情報生命専攻 2018年8月実施 問題11

Author

zephyr

Description

Suppose that a sequence \(\mathbf{x} = x_1 x_2 \cdots x_n\) is generated from a first-order stationary Markov model that has initial probabilities \(\{\pi_k\}\) and transition probabilities \(\{a_{ij}\}\) as follows.

Initial probabilities:

\[ P(x_1 = k) = \pi_k, \quad \text{for } k \in \{0, 1\} \]

Transition probabilities:

\[ P(x_t = j \mid x_{t-1} = i) = a_{ij}, \quad \text{for } i, j \in \{0, 1\}, \quad t = 2, \ldots, n \]

Note that \(P(X)\) is the probability that \(X\) is true, and \(P(X \mid Y)\) is the conditional probability that \(X\) is true when \(Y\) is true.

Answer the following questions:

(1) Assume \(n = 4\). Show the probability that \(101\) is included as a continuous substring in \(\mathbf{x}\). Show also the probability that \(111\) is included as a continuous substring in \(\mathbf{x}\).

(2) Assume \(n = 4\). Show the expected number of 1s in \(\mathbf{x}\) when \(101\) is included as a continuous substring in \(\mathbf{x}\).

In the following questions, use the following transition probabilities.

\[ a_{00} = 0.8, \quad a_{01} = 0.2, \quad a_{10} = 0.3, \quad a_{11} = 0.7 \]

(3) Calculate the expected proportion of 1s in \(\mathbf{x}\) when \(n \to \infty\).

(4) Suppose that \(n = 2m\) (\(m\) is a positive integer). When every two letters of \(\mathbf{x} = x_1 x_2 \cdots x_{2m}\) is converted to a letter of \(\mathbf{y} = y_1 \cdots y_m\) using the following rule, calculate the expected proportions of \(a, c, g, t\) in \(\mathbf{y}\) when \(m \to \infty\).

\[ y_i = \begin{cases} a, & \text{if } x_{2i-1} = 0 \text{ and } x_{2i} = 0, \\ c, & \text{if } x_{2i-1} = 0 \text{ and } x_{2i} = 1, \\ g, & \text{if } x_{2i-1} = 1 \text{ and } x_{2i} = 0, \\ t, & \text{if } x_{2i-1} = 1 \text{ and } x_{2i} = 1, \\ \end{cases} \quad \text{for } i = 1, \ldots, m \]

---

假设序列 \(\mathbf{x} = x_1 x_2 \cdots x_n\) 是从一个一阶平稳马尔可夫模型生成的，该模型具有如下初始概率 \(\{\pi_k\}\) 和转移概率 \(\{a_{ij}\}\)。

初始概率：

\[ P(x_1 = k) = \pi_k, \quad \text{对于 } k \in \{0, 1\} \]

转移概率：

\[ P(x_t = j \mid x_{t-1} = i) = a_{ij}, \quad \text{对于 } i, j \in \{0, 1\}, \quad t = 2, \ldots, n \]

注意 \(P(X)\) 是 \(X\) 为真的概率，\(P(X \mid Y)\) 是 \(X\) 在 \(Y\) 为真时的条件概率。

回答以下问题：

(1) 假设 \(n = 4\)。证明在 \(\mathbf{x}\) 中包含 \(101\) 作为连续子串的概率。也证明在 \(\mathbf{x}\) 中包含 \(111\) 作为连续子串的概率。

(2) 假设 \(n = 4\)。证明在 \(\mathbf{x}\) 中包含 \(101\) 作为连续子串时 \(\mathbf{x}\) 中 1 的期望数量。

在以下问题中，使用以下转移概率。

\[ a_{00} = 0.8, \quad a_{01} = 0.2, \quad a_{10} = 0.3, \quad a_{11} = 0.7 \]

(3) 计算当 \(n \to \infty\) 时 \(\mathbf{x}\) 中 1 的期望比例。

(4) 假设 \(n = 2m\) (\(m\) 是一个正整数)。当 \(\mathbf{x} = x_1 x_2 \cdots x_{2m}\) 的每两个字母转换为 \(\mathbf{y} = y_1 \cdots y_m\) 的一个字母时，使用以下规则，计算 \(\mathbf{y}\) 中 \(a, c, g, t\) 的期望比例，当 \(m \to \infty\) 时。

\[ y_i = \begin{cases} a, & \text{如果 } x_{2i-1} = 0 \text{ 且 } x_{2i} = 0, \\ c, & \text{如果 } x_{2i-1} = 0 \text{ 且 } x_{2i} = 1, \\ g, & \text{如果 } x_{2i-1} = 1 \text{ 且 } x_{2i} = 0, \\ t, & \text{如果 } x_{2i-1} = 1 \text{ 且 } x_{2i} = 1, \\ \end{cases} \quad \text{对于 } i = 1, \ldots, m \]

Kai

(1)

To determine the probability of specific substrings occurring within a Markov sequence, we need to calculate the joint probabilities of these substrings appearing in the sequence.

Probability of \(101\) being included

We consider all possible sequences of length 4 that include \(101\) as a continuous substring:

• \(0101\)
• \(1010\)
• \(1011\)
• \(1101\)

Calculate the probabilities of these sequences:

1. For \(0101\):

\[ P(0101) = \pi_0 \cdot a_{01} \cdot a_{10} \cdot a_{01} \]

1. For \(1010\):

\[ P(1010) = \pi_1 \cdot a_{10} \cdot a_{01} \cdot a_{10} \]

1. For \(1011\):

\[ P(1011) = \pi_1 \cdot a_{10} \cdot a_{01} \cdot a_{11} \]

1. For \(1101\):

\[ P(1101) = \pi_1 \cdot a_{11} \cdot a_{10} \cdot a_{01} \]

The probability of \(101\) being included is the sum of these probabilities:

\[ P(101) = P(0101) + P(1010) + P(1011) + P(1101) = \pi_0 \cdot a_{01} \cdot a_{10} \cdot a_{01} + \pi_1 \cdot a_{10} \cdot a_{01} \cdot a_{10} + \pi_1 \cdot a_{10} \cdot a_{01} \cdot a_{11} + \pi_1 \cdot a_{11} \cdot a_{10} \cdot a_{01} \]

\[ = \pi_0 \cdot a_{01} \cdot a_{10} \cdot a_{01} + \pi_1 \cdot (a_{10} \cdot a_{01} + a_{11} \cdot a_{10} \cdot a_{01}) \]

Probability of \(111\) being included

We consider the sequences of length 4 that include \(111\) as a continuous substring:

• \(0111\)
• \(1110\)
• \(1111\)

Calculate the probabilities of these sequences:

1. For \(0111\):

\[ P(0111) = \pi_0 \cdot a_{01} \cdot a_{11} \cdot a_{11} \]

1. For \(1110\):

\[ P(1110) = \pi_1 \cdot a_{11} \cdot a_{11} \cdot a_{10} \]

1. For \(1111\):

\[ P(1111) = \pi_1 \cdot a_{11} \cdot a_{11} \cdot a_{11} \]

The probability of \(111\) being included is the sum of these probabilities:

\[ P(111) = P(0111) + P(1110) + P(1111) = \pi_0 \cdot a_{01} \cdot a_{11} \cdot a_{11} + \pi_1 \cdot (a_{11} \cdot a_{11} \cdot a_{10} + a_{11} \cdot a_{11} \cdot a_{11}) \]

\[ = \pi_0 \cdot a_{01} \cdot a_{11} \cdot a_{11} + \pi_1 \cdot a_{11} \cdot a_{11} \]

(2)

Given that we need to find the expected number of 1s in the sequence \(\mathbf{x} = x_1 x_2 x_3 x_4\) when the substring \(101\) is included, we need to consider the sequences that include \(101\).

The sequences of length 4 that include \(101\) as a continuous substring are:

• \(0101\)
• \(1010\)
• \(1011\)
• \(1101\)

Let \(P(0101)\), \(P(1010)\), \(P(1011)\), and \(P(1101)\) be the probabilities of these sequences, respectively.

We will calculate the expected number of 1s by averaging the number of 1s in these sequences, weighted by their probabilities.

1. For \(0101\):

\[ \text{Number of 1s} = 2 \]

1. For \(1010\):

\[ \text{Number of 1s} = 2 \]

1. For \(1011\):

\[ \text{Number of 1s} = 3 \]

1. For \(1101\):

\[ \text{Number of 1s} = 3 \]

The expected number of 1s, \(E[\#1s]\), is given by:

\[ E[\#1s] = \frac{2 \cdot P(0101) + 2 \cdot P(1010) + 3 \cdot P(1011) + 3 \cdot P(1101)}{P(101)} \]

Where \(P(101)\) is the total probability of having the substring \(101\):

\[ P(101) = P(0101) + P(1010) + P(1011) + P(1101) \]

Thus, the expected number of 1s is:

\[ E[\#1s] = \frac{2 \cdot P(0101) + 2 \cdot P(1010) + 3 \cdot P(1011) + 3 \cdot P(1101)}{P(0101) + P(1010) + P(1011) + P(1101)} \]

Using the given probabilities:

\[ P(0101) = \pi_0 \cdot a_{01} \cdot a_{10} \cdot a_{01} \]

\[ P(1010) = \pi_1 \cdot a_{10} \cdot a_{01} \cdot a_{10} \]

\[ P(1011) = \pi_1 \cdot a_{10} \cdot a_{01} \cdot a_{11} \]

\[ P(1101) = \pi_1 \cdot a_{11} \cdot a_{10} \cdot a_{01} \]

Substitute these probabilities into the expression for the expected number of 1s:

\[ E[\#1s] = \frac{2 (\pi_0 \cdot a_{01} \cdot a_{10} \cdot a_{01}) + 2 (\pi_1 \cdot a_{10} \cdot a_{01} \cdot a_{10}) + 3 (\pi_1 \cdot a_{10} \cdot a_{01} \cdot a_{11}) + 3 (\pi_1 \cdot a_{11} \cdot a_{10} \cdot a_{01})}{(\pi_0 \cdot a_{01} \cdot a_{10} \cdot a_{01}) + (\pi_1 \cdot a_{10} \cdot a_{01} \cdot a_{10}) + (\pi_1 \cdot a_{10} \cdot a_{01} \cdot a_{11}) + (\pi_1 \cdot a_{11} \cdot a_{10} \cdot a_{01})} \]

(3)

To find the steady-state probabilities \(\pi_0\) and \(\pi_1\), we solve the following system:

\[ \pi_0 = \pi_0 a_{00} + \pi_1 a_{10} \]

\[ \pi_1 = \pi_0 a_{01} + \pi_1 a_{11} \]

\[ \pi_0 + \pi_1 = 1 \]

Substitute the given values:

\[ \pi_0 = \pi_0 \cdot 0.8 + \pi_1 \cdot 0.3 \]

\[ \pi_1 = \pi_0 \cdot 0.2 + \pi_1 \cdot 0.7 \]

\[ \pi_0 + \pi_1 = 1 \]

Solving the system:

\[ \pi_0 = \frac{3}{5}, \quad \pi_1 = \frac{2}{5} \]

The expected proportion of 1s is:

\[ \pi_1 = \frac{2}{5} = 0.4 \]

(4)

Given the rules for \(y_i\):

• \(a\): \(x_{2i-1} = 0\) and \(x_{2i} = 0\)
• \(c\): \(x_{2i-1} = 0\) and \(x_{2i} = 1\)
• \(g\): \(x_{2i-1} = 1\) and \(x_{2i} = 0\)
• \(t\): \(x_{2i-1} = 1\) and \(x_{2i} = 1\)

Calculate the steady-state probabilities for pairs:

\[ P(00) = \pi_0 \cdot a_{00} = \frac{3}{5} \cdot 0.8 = 0.48 \]

\[ P(01) = \pi_0 \cdot a_{01} = \frac{3}{5} \cdot 0.2 = 0.12 \]

\[ P(10) = \pi_1 \cdot a_{10} = \frac{2}{5} \cdot 0.3 = 0.12 \]

\[ P(11) = \pi_1 \cdot a_{11} = \frac{2}{5} \cdot 0.7 = 0.28 \]

The expected proportions are:

• \(a\): \(P(00) = 0.48\)
• \(c\): \(P(01) = 0.12\)
• \(g\): \(P(10) = 0.12\)
• \(t\): \(P(11) = 0.28\)

Knowledge

概率计算 马尔可夫链 转移概率 随机过程

重点词汇

• Markov Model 马尔可夫模型
• Transition Probability 转移概率
• Steady-State 稳态

参考资料

1. "Markov Chains: From Theory to Implementation and Experimentation" by Paul A. Gagniuc
2. "Introduction to Probability Models" by Sheldon M. Ross