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

Author

zephyr

Description

Suppose that a sequence is generated from a first-order stationary Markov model that has initial probabilities and transition probabilities as follows.

Initial probabilities:

Transition probabilities:

Note that is the probability that is true, and is the conditional probability that is true when is true.

Answer the following questions:

(1) Assume . Show the probability that is included as a continuous substring in . Show also the probability that is included as a continuous substring in .

(2) Assume . Show the expected number of 1s in when is included as a continuous substring in .

In the following questions, use the following transition probabilities.

(3) Calculate the expected proportion of 1s in when .

(4) Suppose that ( is a positive integer). When every two letters of is converted to a letter of using the following rule, calculate the expected proportions of in when .

---

假设序列 是从一个一阶平稳马尔可夫模型生成的，该模型具有如下初始概率 和转移概率 。

初始概率：

转移概率：

注意 是 为真的概率， 是 在 为真时的条件概率。

回答以下问题：

(1) 假设 。证明在 中包含 作为连续子串的概率。也证明在 中包含 作为连续子串的概率。

(2) 假设 。证明在 中包含 作为连续子串时 中 1 的期望数量。

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

(3) 计算当 时 中 1 的期望比例。

(4) 假设 ( 是一个正整数)。当 的每两个字母转换为 的一个字母时，使用以下规则，计算 中 的期望比例，当 时。

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 being included

We consider all possible sequences of length 4 that include as a continuous substring:

Calculate the probabilities of these sequences:

1. For :

1. For :

1. For :

1. For :

The probability of being included is the sum of these probabilities:

Probability of being included

We consider the sequences of length 4 that include as a continuous substring:

Calculate the probabilities of these sequences:

1. For :

1. For :

1. For :

The probability of being included is the sum of these probabilities:

(2)

Given that we need to find the expected number of 1s in the sequence when the substring is included, we need to consider the sequences that include .

The sequences of length 4 that include as a continuous substring are:

Let , , , and 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 :

1. For :

1. For :

1. For :

The expected number of 1s, , is given by:

Where is the total probability of having the substring :

Thus, the expected number of 1s is:

Using the given probabilities:

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

(3)

To find the steady-state probabilities and , we solve the following system:

Substitute the given values:

Solving the system:

The expected proportion of 1s is:

(4)

Given the rules for :

• : and
• : and
• : and
• : and

Calculate the steady-state probabilities for pairs:

The expected proportions are:

• :
• :
• :
• :

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