ズンドコ学園入試問題 > 答案 by 7of9

13251 ワード
math #migrated ズンドコキヨシ 数学 Ruby Ruby テキストリンク

ズンドコ学園入試問題

1. 状態遷移図

http://madebyevan.com/fsm/
を利用

2. 平均状態遷移回数 N および平均文字列長 L

参考 吸収的マルコフ過程

2000年にポーランドで仕事に行った後、ユーレイルパスで乗り継ぎながら南フランス Antibesへ行った。そこで会った INRIA の教授が道路の画像解析にマルコフ連鎖モンテカルロを使っていて１時間近く個人レッスンを受けたが、何ひとつ分からなかった。果たしてそのマルコフと関係あるのかどうか。

余談になるが、この時TOEIC900であったが、ポーランドの列車乗り場の人が英語が通じず途方に暮れていたら、横にいたおじさん（英語通じず）が全面的に協力してくれて無事ポーランドから列車に乗れた。
これをきっかけとして、日本で道に迷っている外国人がいれば一日一組限定で道案内する、ということにした。 皆さんもどうぞ。

上記資料の「推移確率行列」

S A B C D Kiyoshi
S 1/2 0 0 0 0 0
A 1/2 0 1/2 0 0 0
B 1/2 0 0 1/2 0 0
C 1/2 0 0 0 1/2 0
D 0 0 0 0 1/2 1/2
Kiyoshi 0 0 0 0 0 1

Kiyoshi列 x S..D行 が行列Uになるのだろうか。 (行列でなく、列ベクトルか）。
その左側が Q になるのだろう。

基本行列

M = (I - Q)^{-1}

5x5の逆行列を求めるのがすごく面倒くさそうだということが分かった。

Octave?やMatlab使いでないので、降参。

Gauss-JordanやLU分解、特異値分解(SVD)など使えばいいらしいが、これらの計算には慣れていない。

行列 M

以下のツールを利用。
http://matrix.reshish.com/inverse.php

S A B C D
S 2 0 0 0 0
A 1.75 1 0.5 0.25 0.25
B 1.5 0 1 0.5 0.5
C 1 0 0 1 1
D 0 0 0 0 2

思った以上に値が見やすい行列になった。

平均吸収時間 Mg

列ベクトル 

g = ( 1, 1, 1, 1, 1, 1 )^{TR}

を行列Mの右側に作用させればいいのだろうか。

これは手計算でできる。

Mg
S 2
A 3.75
B 3.5
C 3
D 2

合計14.25だが、これは「平均状態遷移回数N」なのだろうか。
そうであったとしても、「平均文字列長L」の求め方は分からない。

投げっぱなしジャーマンスープレックス。

計算やり直し

@mpyw さんのコメントによるとRubyで行列計算が簡単にできるようだ。

ideoneでも計算できた。
http://ideone.com/XS2Mzc

推移確率行列

S->Aの部分が0でなく1/2だった。

S A B C D Kiyoshi
S 1/2 1/2 0 0 0 0
A 1/2 0 1/2 0 0 0
B 1/2 0 0 1/2 0 0
C 1/2 0 0 0 1/2 0
D 0 0 0 0 1/2 1/2
Kiyoshi 0 0 0 0 0 1

I-Q

S A B C D
S 0.5 -0.5 0 0 0
A -0.5 1 -0.5 0 0
B -0.5 0 1 -0.5 0
C -0.5 0 0 1 -0.5
D 0 0 0 0 0.5

(I-Q)^(-1)

http://ideone.com/XS2Mzc
と同じになってきた。

S A B C D
S 16 8 4 2 2
A 14 8 4 2 2
B 12 6 4 2 2
C 8 4 2 2 2
D 0 0 0 0 2

Mg

Mg
S 32
A 30
B 26
C 18
D 2

ここで読み方はSのところの32というのが「SからスタートしてKiyoshiになるまでの平均長さ」ということのようだ。

@mpyw さんのコメント

これよりL=N*2+3=67であることも同時に分かる

上記よりLも求まるようだ。

自分は「行と列って縦横どっちだったっけ？状態」だったり「手計算が面倒そう」などの理由から行列を扱う計算は避けてきた。今回の入試問題で行列を扱う良い環境があることを知りよかったと思う。

感謝。