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

标签：

• Tokyo-University
• Pattern-Probability-in-Markov-Sequence
• Stationary-Pair-Frequencies
• Conditional-Probability

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