コイントスの筋の正確な確率
別の問題ユーザが100のコインフリップ6頭または6尾の筋を有する確率を決定しました。彼らが100回のランダムなコイントスを生成する確率を見つけるために、ストリークがあったかどうかを判断します。彼らは、100回のフリップのそのようなシーケンスを10,000回テストして、100回のコインフリップにストリークが発生する可能性が約80％あることを発見しました。
正確な確率を計算することにしました。100回のフリップには\があります$2^{100}\$考えられる結果。パーセンテージを決定するために、ストリークを持っているものの数を計算し、\で割ります$2^{100}\$。
私の素朴な解決策は、数秒で20回のフリップの数を取得します。
from itertools import product
def naive(flips, streak):
return sum('h' * streak in ''.join(p) or
't' * streak in ''.join(p)
for p in product('ht', repeat=flips))
結果：
>>> naive(20, 6)
248384
私の速い解決策は私に100フリップの数を即座に与えます：
from collections import Counter
def fast(flips, streak):
needles = 'h' * streak, 't' * streak
groups = {'-' * streak: 1}
total = 0
for i in range(flips):
next_groups = Counter()
for ending, count in groups.items():
for coin in 'ht':
new_ending = ending[1:] + coin
if new_ending in needles:
total += count * 2**(flips - 1 - i)
else:
next_groups[new_ending] += count
groups = next_groups
return total
アイデアは、まだ進行中のゲームのプールを持つことですが、最後の6回のフリップでグループ化され、そのグループが出現した頻度をカウントします。次に、100回のフリップを一度に1つずつ実行し、グループとそのカウントを更新します。ある時点でストリークで終わるグループはプレイを続行しません。代わりに、それを合計結果に追加します。グループはcount何度も発生し、flips - 1 - i残りのフリップがあり、それらは何でもかまいません。したがってcount、2つのフリップ-1 --iを掛けます。
結果（20回のフリップの結果はナイーブソリューションの場合と同じであることに注意してください）：
>>> fast(20, 6)
248384
>>> fast(100, 6)
1022766552856718355261682015984
そして、2 100で割ると、リンクされた実験と同様のパーセンテージが得られます。
>>> 100 * fast(100, 6) / 2**100
80.68205487163246
コメント、改善のための提案はありますか？
回答
あなたのコードはよさそうだ。読むのは少し難しいですが、大丈夫なコンテキストを考えると！また、new_endingが含まれていない場合needles、コードは\で実行されるように見えることもわかります。$O(f2^s)\$時間、ここで\$f\$であるflipsと\$s\$ですstreak。
私はコードを見ることができますが、コードのif new_ending in needles:実行にかかる時間を短縮します。たとえば、streak = 2の場合、コードを線形時間で実行できますが、数値が大きい場合はあまり役に立ちません。コードは\$O(f2^s)\$。
この最適化をどのように実行しているかを以下で確認できます。HH、TT、HTT、THHなどの子孫を検索していないため、ツリーのサイズが小さくなります。
尻尾は頭の逆であることがはっきりとわかります。頭に焦点を合わせ、「ベース」と「テール」（繰り返しの結果）を分割すると、次のようになります。
HH 1/2^2
H TT 1/2^3
HT HH 1/2^4
HTH TT 1/2^5
HTHT HH 1/2^6
線形時間で実行されるのはクールですが、それほど面白くはありません。したがって、streak = 2の場合、\の合計チャンス$f\$ フリップは：
$$\Sigma_{n=2}^f \frac{2}{2^n}$$
ただし、streak = 3を見ると、特徴的なパターンの始まりがわかります。
HHH 1/2^3
H TTT 1/2^4
HH TTT 1/2^5
HT HHH 1/2^5
HHT HHH 1/2^6
HTH TTT 1/2^6
HTT HHH 1/2^6
HHTH TTT 1/2^7
HHTT HHH 1/2^7
HTHH TTT 1/2^7
HTHT HHH 1/2^7
HTTH TTT 1/2^7
各サイズを数えると、次のようになります。
3: 1
4: 1
5: 2
6: 3
7: 5
これはフィボナッチ数の始まりなので、かっこいいです。最初の30個の値が同じであることを確認しました。これで、streak = 3の方程式があると仮定できます。
$$\Sigma_{n=3}^f \frac{2F(n-2)}{2^n}$$
streak = 4,5,6,10に対して同じことを行うと、次のシーケンスが得られます。
- 4-トリボナッチ
- 5-テトラナッチ
- 6-ペンタナッチ
- 10-フィボナッチ9ステップ
全体として、これはかなり説得力のあるパターンです。そして、\で実行するアルゴリズムを書くことができます$O(fs)\$時間どこ\$f\$フリップと\$s\$ 縞です。
import collections
import itertools
from fractions import Fraction
def fibonacci_nth(size):
store = collections.deque([0] * size, size)
store.append(1)
while True:
yield store[-1]
store.append(sum(store))
def coin_chance(flips, streak):
if streak <= 0 or streak % 1:
raise ValueError("streak must be a positive integer")
if flips < 0 or flips % 1:
raise ValueError("flips must be a non-negative integer")
if streak == 1:
return Fraction(flips != 0, 1)
sequence = (
Fraction(2 * numerator, 2 ** exponent)
for exponent, numerator in enumerate(fibonacci_nth(streak - 1), streak)
)
return sum(itertools.islice(sequence, flips - streak + 1))
# Code to get OEIS sequences
def funky_finder(depth, size):
desired = (['H'] * size, ['T'] * size)
stack = [iter("HT")]
stack_value = []
while stack:
try:
coin = next(stack[-1])
except StopIteration:
stack.pop()
if stack_value:
stack_value.pop()
continue
_stack_value = stack_value + [coin]
if _stack_value[-size:] in desired:
yield ''.join(_stack_value)
elif len(stack) < depth:
stack_value.append(coin)
stack.append(iter('HT'))
# I know, I know. But I was using this in a REPL!
size = 3; [i // 2 for i in sorted(collections.Counter(len(i) - size for i in funky_finder(20 + size, size)).values())]
>>> 100 * fast(20, 6) / 2**20
23.687744140625
>>> 100 * float(coin_chance(20, 6))
23.687744140625
>>> 100 * fast(100, 6) / 2**100
80.68205487163246
>>> 100 * float(coin_chance(100, 6))
80.68205487163246