Last active
January 4, 2024 03:53
-
-
Save recuraki/4fc88626744210f760a95288d9392910 to your computer and use it in GitHub Desktop.
おみくじ
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
""" | |
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)] | |
以上を考えると、「大吉の在庫がまだ残っている確証があれば」いつ引いても確率は同じである。 | |
ただし、大吉がいくら含まれているかの観測ができない場合、含まれていない場合に引く可能性があるので | |
(一般的に大吉は必ず1本以上は入っているだろうから/要出典)最初に引いた方がよい | |
""" |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment