CBMS-2019-11

题目来源：[[做题/文字版题库/CBMS/2019#Question 11|2019#Question 11]] 日期：2024-07-26 题目主题: CS-概率论-马尔可夫模型

解题思路

本题涉及一阶马尔可夫模型的概率计算以及期望值的求解。以下是具体步骤：

1. 计算包含指定子串的序列的概率。
2. 计算指定条件下的期望值。
3. 使用给定的转移概率计算无穷长度序列的状态比例。
4. 通过转换规则计算新的序列中各字母的期望比例。

Solution

Question 1: Probability that $101$ and $111$ are included as continuous substrings in $\mathbf{x}$ when $n=4$

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}$$

Question 2: Expected number of 1s in $\mathbf{x}$ when $101$ is included as a continuous substring

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})}$$

Question 3: Expected proportion of 1s in $\mathbf{x}$ when $n\to \infty$

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},{\pi }_1=\frac{2}{5}$$

The expected proportion of 1s is:

$${\pi }_1=\frac{2}{5}=0.4$$

Question 4: Expected proportions of $a,c,g,t$ in $\mathbf{y}$ when $m\to \infty$

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$

知识点

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

重点词汇

• 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