おみくじ

omikuji.py

"""
https://twitter.com/recuraki/status/1741709264471937422

大吉の入ったおみくじがある。おみくじは引かれると消費される。
他の参拝者は大吉を引くまで連続しておみくじを引く。
この時、自分がおみくじを最初に引くのと後で引くので大吉を引く確率は異なるか？
自分を含めて参拝者は他の参拝者の結果を見て引く引かないを決めない。
↓

n, m: 全体, 大吉の数
とする。
dp[i][j]は全体がi枚存在してjの大吉が残っている状態の確率とする。dp[n][m] = 1であり、その他の初期値を0とする。
"""
from fractions import Fraction
from pprint import pprint
n = 10
m = 3
dp = [[0 for _ in range(m+1)] for _ in range(n+1)]
dp[n][m] = Fraction(1,1)
# n, mの状態から遷移させる
for i in range(n, 0, -1): # 全体の数
    for j in range(m, 0, -1): # あたりの数
        ptmp = Fraction(1,1) # k-1を引いて大吉でない状態
        for k in range(1, i-j+1 + 1): # i,jの状態から、k枚を引いた時に大吉である
            # k枚を引いた時に大吉な確率は、ptmp * (j / 残りの数)
            dp[i-k][j-1] += ptmp * Fraction( j , i-k+1) * dp[i][j]
            # k-1を引いて大吉でない確率をupdateする。
            ptmp *= Fraction(i-k+1 - j , i-k+1)

pprint(dp)

# p[i] = i枚が残っている時に次に大吉を引く確率
p = [0] * (m+1)
for j in range(m+1):
    for i in range(1, n+1):
        p[j] += (Fraction(j , i) * dp[i][j] )

pprint(p)

"""
10, 3(10枚の中に3枚のあたりがある場合)
[[Fraction(3, 10), 0, 0, 0],
 [Fraction(7, 30), Fraction(1, 15), 0, 0],
 [Fraction(7, 40), Fraction(7, 60), Fraction(1, 120), 0],
 [Fraction(1, 8), Fraction(3, 20), Fraction(1, 40), 0],
 [Fraction(1, 12), Fraction(1, 6), Fraction(1, 20), 0],
 [Fraction(1, 20), Fraction(1, 6), Fraction(1, 12), 0],
 [Fraction(1, 40), Fraction(3, 20), Fraction(1, 8), 0],
 [Fraction(1, 120), Fraction(7, 60), Fraction(7, 40), 0],
 [Fraction(0, 1), Fraction(1, 15), Fraction(7, 30), 0],
 [Fraction(0, 1), Fraction(0, 1), Fraction(3, 10), 0],
 [0, 0, 0, Fraction(1, 1)]]

i枚の大吉が余っている時にあたりを引く確率(初期状態 10枚のうち、あたり3として)
[Fraction(0, 1), Fraction(3, 10), Fraction(3, 10), Fraction(3, 10)]

以上を考えると、「大吉の在庫がまだ残っている確証があれば」いつ引いても確率は同じである。
ただし、大吉がいくら含まれているかの観測ができない場合、含まれていない場合に引く可能性があるので
（一般的に大吉は必ず１本以上は入っているだろうから/要出典）最初に引いた方がよい
"""