跳到主要内容

京都大学 情報学研究科 知能情報学専攻 2022年8月実施 専門科目 S-4

Author

Isidore, Passed, 祭音Myyura

Description

Let be an alphabet for information sources. Assume that irreducible and aperiodic Markov information sources and consisting of finite numbers of states satisfy:

  • [C1] neither nor outputs any sequence including , and
  • [C2] does not output any sequence including .

Answer all of the following subquestions from (1) to (5).

(1) Let be the states of . Draw the transition diagram of . Assume that should output with probability () when it is at state . You must make the number of the states minimum.

(2) Let be the states of . Draw the transition diagram of . Assume that should output with probability () when it is at state and with probability () when it is at state . You must make the number of the states minimum. Also explain the reason why your answer satisfies [C1] and [C2].

(3) Give the transition matrix of .

(4) Let a probability distribution be on the states . When the distribution is stationary and , represent each of with .

(5) Show the entropy of with when the initial distribution is equal to the stationary distribution given in (4).

Kai

(1)

(2)

(3)

(4)

(5)

Let denote the entropy function

hence