Togetter/min.tを安心してお使い頂くためのガイドラインを公開しました。
編集可能
2016年6月2日

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

コイン投げを繰り返すとき,表(裏)が3回連続で出るパターンを数え上げるとトリボナッチ数列が現れることを(個人的に)発見したのでまとめます。 組合せ論的には周知のことかも…。よりエレガントな解法あれば是非お知らせください!
17
{3,5/2} 大二十面体 @Polyhedrondiary

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

2016-06-01 05:01:04
{3,5/2} 大二十面体 @Polyhedrondiary

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

2016-06-01 07:58:27
拡大
{3,5/2} 大二十面体 @Polyhedrondiary

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

2016-06-01 08:03:37
{3,5/2} 大二十面体 @Polyhedrondiary

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

2016-06-01 08:11:02
拡大
{3,5/2} 大二十面体 @Polyhedrondiary

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

2016-06-01 08:11:21
拡大
{3,5/2} 大二十面体 @Polyhedrondiary

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

2016-06-01 08:16:38
るふぁ @lpha_z

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

2016-06-01 08:23:43
{3,5/2} 大二十面体 @Polyhedrondiary

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

2016-06-01 08:25:28
{3,5/2} 大二十面体 @Polyhedrondiary

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

2016-06-01 21:01:41
{3,5/2} 大二十面体 @Polyhedrondiary

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

2016-06-01 21:11:14
{3,5/2} 大二十面体 @Polyhedrondiary

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

2016-06-01 21:17:12
{3,5/2} 大二十面体 @Polyhedrondiary

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

2016-06-01 21:19:31
{3,5/2} 大二十面体 @Polyhedrondiary

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

2016-06-01 23:16:02
{3,5/2} 大二十面体 @Polyhedrondiary

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

2016-06-01 23:18:02
{3,5/2} 大二十面体 @Polyhedrondiary

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

2016-06-01 23:21:56
{3,5/2} 大二十面体 @Polyhedrondiary

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

2016-06-01 23:34:50
拡大
{3,5/2} 大二十面体 @Polyhedrondiary

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

2016-06-02 07:59:21
{3,5/2} 大二十面体 @Polyhedrondiary

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

2016-06-02 08:05:25
{3,5/2} 大二十面体 @Polyhedrondiary

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

2016-06-02 08:09:55
るふぁ @lpha_z

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

2016-06-02 09:54:08
るふぁ @lpha_z

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

2016-06-02 10:12:23
るふぁ @lpha_z

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

2016-06-02 10:54:41
{3,5/2} 大二十面体 @Polyhedrondiary

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

2016-06-02 12:15:03
{3,5/2} 大二十面体 @Polyhedrondiary

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

2016-06-02 21:33:30
残りを読む(6)

コメント

Dcdcxr @Dcdcxr 2016年6月2日
前提となる情報がなくて理解できない。
0
うてん @uten73 2016年6月2日
ダイスの目の内3つをUP 残り3つをDOWNとし、各プレイヤーは「UDD」「DUD」など、ダイス3回分の目を予想する。  続いてダイスを連続で振り、DUDDDUU…(ry と出していく。  先に自分の予想したパターンが出れば勝ち。(この場合だとDUDが1番 UDDが2番 DDDが3番目…(ry に出ている)
0
うてん @uten73 2016年6月2日
そしてこのツイート主さんはDDU UUDなどの1:2比率の期待値が8回 DDD UUUの3:0比率の期待値が14回で合ってるのかどうか検証されている訳です(*´ω`*)
0
重い槍 @omoiyari219 2016年6月2日
前提となる情報があっても理解できない…
0
一二三🚗いちもんじふみカー @giko_t 2016年6月2日
確率の錯誤でぐぐっても心理学かギャンブラーの錯誤しか出てこないなー
0
KZRNM @naminodarie 2016年6月2日
1:2の期待値<0:3の期待値は直感的になんとなくわかるけど、UDUパターンとUDDパターンが同じ期待値であることは直感的ではなくてそこが気になるところだから、漫画の"誤謬"はなんか不自然だと思った
1
KZRNM @naminodarie 2016年6月2日
よく見たらまとめ内でもUDUパターンの考察はしてなかったですね
0
KZRNM @naminodarie 2016年6月2日
状態遷移図で考えるとなんとな~くUUD型<UDU型<UUU型なのが想像できる https://pic.twitter.com/CWRq9eaDmv
0
レッドほむ @red_hom 2016年6月2日
UDを(期待値上)4回でクリアして5回目で最後のUがクリアor全リセ勝負だから(期待値上)2周して10回
0
{3,5/2} 大二十面体 @Polyhedrondiary 2016年6月2日
10回が正解で良さそうです。のちほどまとめ更新します
0
{3,5/2} 大二十面体 @Polyhedrondiary 2016年6月2日
まとめを更新しました。DDUとDUDについても確認できました。
0
Kawai_Yusuke @fiddler_K 2016年6月3日
出やすい組み合わせと出にくい組み合わせか。面白いけど、組み合わせ論がまだちゃんと理解できてない。。。
0
一二三🚗いちもんじふみカー @giko_t 2016年6月3日
数学的な証明ってこれで合ってるん?三連続型や交互型より二連続型の組み合わせの方が出やすいってのは興味深いけど。
0