確率モデル検査器PRISMは様々な確率的なモデルに関する性質を調べるためのツールです.
その中でもDTMC(離散時間マルコフ連鎖)のモデルについての例題を使ってひと通り遊んでみます.
用いる例題はこちらのものです.
PRISM Tutorial
DTMCは確率的に状態遷移をするモデルです.
例題として表と裏の2面しかないコインを用いて6面のサイコロを再現するアルゴリズムを使います(Knuth and Yao [KY76]).
下の図のように確率的に状態遷移をすると最終状態にたどりつく確率はすべて1/6になります.
これを式で求めることもできますが,ここではこのことをPRISMを用いて確率を求めます.
PRISMのGUIを起動してエディタに以下のように入力しました.
ここでは,原典のものと一部異なりますが,後の実験のためにこのようにしました.
dtmcmodule die// local states : [0..8] init 0;// value of the died : [0..6] init 0;[] s=0 -> 0.5 : (s'=1) + 0.5 : (s'=2);[] s=1 -> 0.5 : (s'=3) + 0.5 : (s'=4);[] s=2 -> 0.5 : (s'=5) + 0.5 : (s'=6);[] s=3 -> 0.5 : (s'=1) + 0.5 : (s'=7) & (d'=1);[] s=4 -> 0.5 : (s'=7) & (d'=2) + 0.5 : (s'=7) & (d'=3);[] s=5 -> 0.5 : (s'=7) & (d'=4) + 0.5 : (s'=7) & (d'=5);[] s=6 -> 0.5 : (s'=2) + 0.5 : (s'=7) & (d'=6);[] s=7 -> (s'=8);[] s=8 -> (s'=8);endmodule
下のタブから Properties のタブを選択し画面を切り替えます.
Properties の白いボックスで右クリックをして「Add」を選択します.
そうするとダイアログが出るので Property にモデルでチェックしたいことを書きます.
P=?[F s=8&d=x ]
これは将来的(F)にs=8かつd=xになる確率は?というような意味です.
Okeyを押すと何やらエラーが出ますが,xが定義されていないよという意味なので.
とりあえずそのダイアログを Yes で閉じた後に
Properties の白いボックスのしたの Constats というところで設定します.
Constatsの枠の中で右クリックをして「Add constants」を選択します.
そうしたら,Name の場所が「C0」となっていると思うので「x」に書き換えてください.
Value は空欄のままにしておいてください.
これで準備は整ったので
右の Experiments のボックスの中で右クリックをして「New Experiment」を選択します.
すると,xの範囲を指定する画面が開きます.
ラジオボタンをRangeの方に切り替えて End を 6 に設定してOkayを押します.
グラフの書き方を聞いてきますがとりあえずそのまま Okey にします.
すると,d=0で0となり,残りで0.1666...ぐらいとなっているグラフが描かれると思います(下図).
これがdの値がそれぞれの値になる確率になります.
dが1~6をとるサイコロの目のような振る舞いをすることがわかると思います.
次に,サイコロの目の期待値の計算をこのモデルを用いて行なってみます.
サイコロの目の期待値は1×1/6+2×1/6+3×1/6+4×1/6+5×1/6+6×1/6となり,7/2となるのが正しい値です.
下のタブを Model に戻して以下の式を追加します.
rewards "steps"[] (s=7): d;endrewards
この意味はs=7でd(サイコロの目)の値だけ「報酬」をあげるという意味です.
そして Properties の式をダブルクリックすると再び先ほどのダイアログが開くので以下の用に変更します.
R=?[F s=8 ]
先ほど「P」だったのが「R」になっていることに注意してください.
これは s=8 になった時の「報酬」の期待値は?という意味です.
そしてOkeyを押して閉じたら Properties の式を右クリックしてください.
メニューのVerifyを押すと,ダイアログが開きます.
この時,Result (expected reward) が期待値になります.
3.49999....
のような値が表示され,ほぼ7/2になっていることが確認できると思います.
以上がPRISMを用いたDTMCのモデルチェックの基本的な使い方です.
他にもPRISMには様々な機能があるので使ってみてください.
その他・感想
PRISMのUIは変な所で右クリックをしなければいけないという特徴があり,ちょっとなれないと使いにくい部分がありました.それ以外は普通に使うことができ,研究用のツールとしてはかなり良い出来の用に思いました.
続きを読む: 確率モデル検査器PRISMを使ってみる(DTMC)