コイン投げの確率とトリボナッチ数列

{3,5/2} 大二十面体 @Polyhedrondiary

【本棚登録】『賭ケグルイ双(1) (ガンガンコミックスJOKER)』河本 ほむら booklog.jp/item/1/4757548… #booklog

{3,5/2} 大二十面体 @Polyhedrondiary

『賭ケグルイ双』のこの確率問題面白い。 最初にその順列が出るまでに必要な回数の期待値が異なるので，選ぶ順列によって有利不利があるって話。 p.twipple.jp/g0meM twitter.com/Polyhedrondiar…

拡大

{3,5/2} 大二十面体 @Polyhedrondiary

この期待値8回と14回が正しいかどうかは未確認。明快な証明あるのかな？

{3,5/2} 大二十面体 @Polyhedrondiary

さらに自分と相手の手の組合せで勝率が大きく変わってくる。 例えばUUU対DUUだと，しょっぱなからUが3回出ないとUUUは勝てず，勝率わずか1/8。(それ以外でUUUが出るには直前にDが出てる必要があって，既に負けてる) p.twipple.jp/Nt1vY

拡大

{3,5/2} 大二十面体 @Polyhedrondiary

2個の順列で先に出るのを選ぶケースの勝率表は，こんな感じになる。 UU対DU，DD対UDが非対称(ゾロ目の方は勝率1/4)になるので，相手が何も考えてなければ，DUかUDが最善手ということになる。 p.twipple.jp/DCEeP

拡大

{3,5/2} 大二十面体 @Polyhedrondiary

【緩募】一連のコイン投げに現れる裏表3個の順列を当てるゲームで，二者のうち先に出現した方を勝ちとする場合の，全組合せに対する勝率表 (どこかに落ちてそう…？)

るふぁ @lpha_z

@Polyhedrondiary 「数学」じかけのパズル&ゲーム : 「1人遊び」で夜も眠れず という本にベストな戦略だけなら載っています

{3,5/2} 大二十面体 @Polyhedrondiary

@lpha_z ほんとですか？ありがとうございます！

{3,5/2} 大二十面体 @Polyhedrondiary

コイン投げの確率。 「表表表」が初出するまでの回数n(>=3)に対して，その場合の数a_nを考えると，数列{a_n}はひょっとしてトリボナッチ数列になるのでは？のでは？

{3,5/2} 大二十面体 @Polyhedrondiary

トリボナッチ数列って，前3項の和をとっていった数列{1,1,2,4,7,13,24,44,…}で，「表が(Uが)連続3回」に対応してる。 そうだとすると，UUUが初めて出るまでの回数の期待値って，14じゃなくて12になるっぽい。 twitter.com/Polyhedrondiar…

{3,5/2} 大二十面体 @Polyhedrondiary

n(>3)回でUUUが初出したときのパターン(必ずDUUUで終わる)は，次のいずれか。漏れも重複もない。 ①n-1回で初出のときのパターンの冒頭にDをつけたもの ②n-2回で初出のときのパターンの冒頭にUDをつけたもの ③n-3回で初出のときのパターンの冒頭にUUDをつけたもの

{3,5/2} 大二十面体 @Polyhedrondiary

なぜなら， Dで始まるn回初出列は①で尽くされてるし， UDで始まるn回初出列は②で， UUDで始まるn回初出列は③で尽くされるから。 そしてそのほかにはn回初出列は存在しない(当然UUUで始まることはできない)。 (説明不足，間違い等あったら御指摘歓迎です)

{3,5/2} 大二十面体 @Polyhedrondiary

次にDUUが初めて出るまでの数え上げ。 n(>3)回投げてDUUが初出したときのパターンは，次のどれか。 ①n-1回で初出のときのパターンのDUUの直前にDを挿入したもの ②n-2回で初出のときのパターンのDUUの直前にDUを挿入したもの ③末尾のDUU以外は全てUであるもの

{3,5/2} 大二十面体 @Polyhedrondiary

なぜなら， DDUUで終わるn回初出列は①で尽くされてるし， DUDUUで終わるn回初出列は②で尽くされてて， UUDUUで終わるn回初出列は，それ以上のDをもたない(もつなら末尾以外のDUUが存在してしまう)ので③で尽くされてるからだ。 これで漏れもダブリもない。

{3,5/2} 大二十面体 @Polyhedrondiary

よって，DUUが初出する場合の数は，前2項に1を足していく数列{1,2,4,7,12,20,33,54}になる。これはフィボナッチ数列から1を引いたものに一致。 "UUU"ではU3連でトリボナッチだったけど，今回はD"UU"とUの2連があるのでフィボナッチが現れるっぽい。

{3,5/2} 大二十面体 @Polyhedrondiary

あっ，勘違い…！

{3,5/2} 大二十面体 @Polyhedrondiary

ここからDUU初出までの試行回数の期待値を求めると，8という計算になる。(さっきのUUUの方も14で合ってた) 結局，『賭ケグルイ双(1)』のこのセリフは正しく，期待値は8回と14回であることを確かめることができた。 p.twipple.jp/OlBGx

拡大

{3,5/2} 大二十面体 @Polyhedrondiary

DDUでも同じになることは，自明…ではないのかな。 あと，これは漫画でも言及なかったけど，DUDが初出するまでの試行回数期待値はいくつだろう？12より小さいのはいいとして，8より大か小か。

{3,5/2} 大二十面体 @Polyhedrondiary

【緩募】一連のコイン投げで，「表裏表」のパターンが初めて出るまでの試行回数の期待値はいくつ？

{3,5/2} 大二十面体 @Polyhedrondiary

【緩募】あるいは，試行回数を3から増やしていくとき，「表裏表」初出パターンの種類の数はどんな数列に従う？ 最初の7項は，{1,2,3,5,9,15,28,…}と思うんだけど，これOEISに入れても適当な数列ヒットしないんだよね…。

るふぁ @lpha_z

@Polyhedrondiary 15ではなく16のようです。 [任意2文字]DDUUDU、[DDD、DDU、DUU、UUU、UDD]UUUDU、[UDU以外]DDUDU、の16種です。

るふぁ @lpha_z

@Polyhedrondiary a[n+3]=2a[n+2]-a[n+1]+a[n]のような漸化式になるようです。この係数列は、冗長2進表現としてみると7になり、UUUの時のトリボナッチ数列と同じになりますね。

るふぁ @lpha_z

@Polyhedrondiary 10回ではないでしょうか。これは、漸化式の係数列の各桁[2,-1,1]に[3,4,4]をかけて得られる、7に3を足したもので、UUUの時も同様な方法でいけます。[3,4,4]はn2^(3-n)で得られる数列です。

{3,5/2} 大二十面体 @Polyhedrondiary

@lpha_z 数え間違いすみません😣💦⤵ その漸化式で良さそうですね。 1つ前の冒頭にDかUをつけた順列のうち，2つ前のDで始まる順列の冒頭にDUをつけたもの(個数は2つ前の個数と3つ前の個数の差)になりますから。 のちほどまとめ更新したいと思います！

{3,5/2} 大二十面体 @Polyhedrondiary

@lpha_z 文意不明でした 「1つ前の冒頭にDかUをつけた順列のうち，2つ前のDで始まる順列の冒頭にDUをつけたもの"は不適ということ"になりますから」と読み替えてもらえれば。 それと期待値は確かに10回になりますね。どれも整数になるなんて綺麗…！