かなり適当な不定期日記(仮)
――日々の思いや出来事の織り成すカオスを言語化してみる。
スポンサーサイト
--月--日 (--)
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
「たいへんたいジェネレーター」について(計算含む)
09月16日 (火)
プログラミングの各過程の復習、兼、JavaScriptとかCSSとかの習作としてつくった、

たいへんたいジェネレーター
https://googledrive.com/host/0B9f3hv6KkjXcS19ZMmxxdGE5bUE/THM/tht-gen.html 
https://yk0242.github.io/incubation/incubation-js/THM/tht-gen.html


上記ツイート後に、ツイッター連携を追加したので、極端に長かったり短かったりの、興味ある結果が出たら、結果表示から直接ツイートできるようにもしてあったり。

類似プログラムを見て興味を持ったので、自分もちょっと足して作ってみたパターン。
(参考にしたプログラムとかは実際のページの下部参照。)

バグ報告や改善案、感想等はcatmark_yygm.pngへメールか、もしくは @kitamiya へツイートして下さい。



以下、統計結果とかその数的根拠の計算とか。





まずは、目標が「たいへん」のみの場合から考えます。

単純思考で、各文字の出現確率が 1/4 なので、これが四回連続で起きる、 (1/4)^4 = 1/256 が確率で、即ち256文字に一回出現する、と考える事もできます。


もう少し詳しく考えてみると、答えが違ってくる可能性もあります。

とりあえずこの「コインで五回連続で表が出るまでの回数について(英語)」の質問を参照してみて、その回答の中でも、期待長を e として、各ケースの確率を足していく方法を、今回の場合に適応してみます。


「た」「い」「へ」「ん」をランダム出力していって、
「たいへん」が出るまでの期待長をe とします。
そして、「た」が出た状態から、「たいへん」が出るまでの期待長をf とします。

各ケースでの期待長の変遷と、そのケースが起こる確率は、以下の通りです:


上の表がe の計算用、下の表がf の計算用です。

この場合、e 及びf は、対応する表の(各行の 出現確率x期待長)の和 となります。

まずは上の表から、



と得られます。

また、下の表から、



と得られます。

(2)の式と(1')の式の差を取って、



これを(1)の式に代入し戻すと、


(なおf = 253


この結果であるe = 256 は、最初にあった単純思考からの数値と、(たまたま)一致しています。



この手法と結果について、完全に自信があるわけではなかったので、念の為Maths Stack Exchange にも質問してみました:
http://math.stackexchange.com/questions/931839/expected-number-of-output-letters-to-get-desired-word (英語)

ここで、他の解法も提示されているので、興味があったらどうぞ。
中でも、マルコフ連鎖のTransition Matrixを用いた方法は、単純で面白いです。



また、プログラムを用いた実測値としても、256文字に一回の値が得られました:






今度は、実際の「たいへんたいジェネレーター」と同じように、「たいへん」もしくは「へんたい」が出現するまでの期待長を、同様の手法で計算してみます。


始める前に、プログラムを用いた実測値を確認してみましょう。

単純思考で、どちらか一方が出る確率が 1/256 、ならどちらかが出る確率はその倍で 1/128 、従って期待値は 128 、と考えられますが…

ss_20140915_165631.png

なんと、136 が期待長らしいです…


では計算してみましょう。


「た」「い」「へ」「ん」をランダム出力していって、
「たいへん」「へんたい」が出るまでの期待長をe とし、
「た」が出た状態から、「たいへん」「へんたい」が出るまでの期待長をf とし、
「へ」が出た状態から、「たいへん」「へんたい」が出るまでの期待長をg とします。

各ケースでの期待長の変遷と、そのケースが起こる確率は、以下の通りです:

e の計算用:


f の計算用:


g の計算用の表は、f のそれと同様です。(表掲載略)


第一例に倣って、各テーブルで (対応する確率と期待長の積)の和 が、それぞれ対応するefg の値となります。

fg の計算結果は、以下のようになります:



二つ目の表から(1)の式が、省略した表から(2)の式が得られます。
そして、二式の合成により、(期待通りに)同じ式がf 及びにg の値となります。

更に、一つ目の表からe の式を導くと、



と出るので、ここに(3)式を代入して、e = 136 f = g = 135 と言う結果が出ます。


数式的にも、実測値と同じ 136 が導き出されました。

直感的計算が、必ずしも正しいとは限らないという一例でした。




なお、Transition matrixを用いた手法は、この例にも適用できます。
この手法で試した図が、こちらとなります:



以上、「たいへんたいジェネレーター」に関するおはなしでした。
コメント
この記事へのコメント
コメントを投稿する
URL:
Comment:
Pass:
<FC2 BLOG の HTTPS 対応まで暫定的にテキストボックスにしています> ...
秘密: 管理者にだけ表示を許可する
 
トラックバック
この記事のトラックバックURL
この記事へのトラックバック

copyright © 2005- , yk. all rights reserved.
Powered by FC2ブログ.
/ 無料カウンター
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。