問題設定

ビンゴゲームのように、最初に成功状態になった人が報酬を得られるような状況を考える。自分含め参加者が$N$人いるとする。$N$人の中で自分が最初に成功状態になり報酬を得ることができる確率を計算する。ただし同時刻に最初に成功状態になった人数が$m$人いる時、等しく$1/m$の確率で1位の人を決め、1位の人のみが報酬を得られるとする。
この記事では、自分と他の参加者について各時刻で初めて成功状態になる確率がそれぞれわかっている際に、自分が1位になる確率はいくつか計算する方法を導出する。この設定での計算はは例えばビンゴゲームであればある程度ゲームが進んで自分のビンゴカードの状態がどの程度良いか判断するために使える。自分の各時刻で成功状態になる確率はその状態からモンテカルロシミュレーションなどで各時刻における確率を予測した確率値、他の参加者はゲームが始まった初期状態からモンテカルロシミュレーションを行って計算される各時刻における確率を予測した確率値を使って、自分がその状態から1位になる確率を計算できる。
参加人数$N$が多い場合、全員分のシミュレーションをするコストは大きい。そのため、自分の確率を他者の確率だけをシミュレーションで正確に予測しておき、それを使って自分が1位になる確率を直接計算することには計算コスト面の意味がある。また、$N$は大きい数のため、$N$個の値の和を計算して和を計算するような処理も可能な限り避ける。
さらに、この記事では有利になるように複数人でチームを組み、チームの誰かが1位になった際にその報酬を山分けする条件で、報酬の期待値を計算する方法も導出する。

定式化

現在時刻を$t=0$として、$t=0$においてはまだ誰も成功状態になっていないとする。
自分が初めて成功状態となる時刻の確率変数を$X$とし、自分以外の参加者$j=1,2...,N-1$の初めて成功状態となる時刻の確率変数を$Y_j$とする。自分が時刻$t$に初めて成功状態になる確率は$P(X=t)$、参加者$j$が時刻$t$に初めて成功状態になる確率は$P(Y_j=t)$と表される。
確率変数$X, Y_1,...,Y_{N-1}$は独立とする。また、他の参加者については全ての時刻について参加者間で確率が等しいとする。つまり$P(Y_1=t)=...=P(Y_{N-1}=t)$。

複数人で組むケースも定式化する。$K$人で組むとする。他の参加者は$N-K$人となる。この場合、時刻とその時刻でチーム内で成功状態になる人数についての2変数確率変数$X$を考え、時刻$t$に$k$人が成功状態となる確率を$P(X=(t, k))$と表す。このようにする理由は、チーム内については個々のチームメンバーの状態は独立でなく、個々のチームメンバーについての確率の積で単純に表せない状況を想定しているからである。他の参加者$j=1,2...,N-K$については同様に初めて成功状態となる時刻の確率変数を$Y_j$として、$X, Y_1,...,Y_{N-1}$は独立とする。

導出

自分が1位になる確率

時刻$t$において自分が成功状態になり、他の参加者$N-1$人のうち$m$人が成功状態になる確率を計算する。この確率は他の参加者$N-1$人から$m$人を選ぶ選び方を考慮し、

P(X=t)P(Y=t)^m P(Y>t)^{N-m-1} \binom{N-1}{m}

となる。なお、二項係数$\binom{N-1}{m} = \frac{(N-1)!}{m!(N-m-1)!}$を用いている。また、$P(Y_1=t)=...=P(Y_{N-1}=t)$なので、$Y$の添字を省略して$P(Y=t)$で表した。
この場合、時刻$t$で同時に最初に成功状態になっている参加は自分含め$m-1$人なので、自分が1位になる確率はその$\frac{1}{m+1}$である。
$0 \le m \le N-1$があり得るので、時刻$t$において自分が1位になる確率の合計は、

\sum_{m=0}^{N-1} P(X=t)P(Y=t)^m P(Y>t)^{N-m-1} \binom{N-1}{m} \frac{1}{m+1}

である。これを$E_t$とする。求めたい自分が1位になる確率は$\sum_{t} E_t$である。
これを式変形する。まず、

\begin{align}
\binom{N-1}{m} \frac{1}{m+1} &= \frac{(N-1)!}{m!(N-m-1)!} \frac{1}{m+1} \\
&= \frac{(N-1)!}{(m+1)!(N-m-1)!} \\
&= \frac{1}{N} \frac{N!}{(m+1)!(N-m-1)!}
\end{align}

であるから、

\begin{align}
E_t = &\sum_{m=0}^{N-1} P(X=t)P(Y=t)^m P(Y>t)^{N-m-1} \binom{N-1}{m} \frac{1}{m+1} \\
= & \frac{1}{N} P(X=t) \sum_{m=0}^{N-1} P(Y=t)^m P(Y>t)^{N-m-1} \frac{N!}{(m+1)!(N-m-1)!} \\
= & \frac{1}{N} P(X=t) \sum_{m=0}^{N-1} P(Y=t)^m P(Y>t)^{N-m-1} \binom{N}{m+1} \\
\end{align}

となる。
$P(Y=t)=0$ならば、$\sum_{m=0}^{N-1}$の内側は$m=0$以外$0$になるので、$E_t=P(X=t)P(Y>t)^{N-1}$である。
$P(Y=t)>0$ならば、

\begin{align}
E_t = & \frac{1}{N} P(X=t) \frac{1}{P(Y=t)} \sum_{m=0}^{N-1} P(Y=t)^{m+1} P(Y>t)^{N-m-1} \binom{N}{m+1} \\
= & \frac{1}{N} P(X=t) \frac{P(Y \ge t)^N - P(Y > t)^N}{P(Y=t)} 
\end{align}

となる。式変形には二項定理と$P(Y=t) + P(Y>t) = P(Y \ge t)$を用いた。

したがって、時刻$t$で自分が1位になる確率$E_t$は、

E_t = \begin{cases}
P(X=t)P(Y>t)^{N-1} & (P(Y=t) = 0) \\
P(X=t) \frac{P(Y \ge t)^N - P(Y > t)^N}{N P(Y=t)}  & (P(Y=t) > 0)
\end{cases}

であり、自分が1位になる確率の全体はこれを用いて$\sum_{t} E_t$となる。

複数人でチームを組む場合

時刻$t$においてチーム内の$K$人のうち$k$人が成功状態になり、他の参加者$N-K$人のうち$m$人が成功状態になる確率を計算する。この確率は他の参加者$N-K$人から$m$人を選ぶ選び方を考慮し、

P(X=(t, k))P(Y=t)^m P(Y>t)^{N-K-m} \binom{N-K}{m}

ただし、1人の場合と同様に$P(Y_1=t)=...=P(Y_{N-K}=t)$なので、$Y$の添字を省略して$P(Y=t)$で表した。
この場合、チーム内の誰かが1位になる確率は$\frac{k}{k+m}$である。
$1 \le k \le K, 0 \le m \le N-K$があり得るので、時刻$t$において自分が1位になる確率の合計は、

\sum_{k=1}^{K} \sum_{m=0}^{N-K} \frac{k}{k+m} P(X=(t,k)) P(Y=t)^m P(Y>t)^{N-K-m} \binom{N-K}{m}

と表せる。これを$E_t$とする。求めたいのはチームメンバーの誰かが1位になった場合に得られる報酬を$K$人で山分けする場合の報酬の期待値である。1位となった際の報酬を$1$とおくと、求めたい値は$\frac{1}{K} \sum_{t} E_t$で計算できる。
$P(Y=t)=0$ならば$\sum_{m=0}^{N-1}$の内側は$m=0$の場合以外は$0$になるので、

E_t = P(Y>t)^{N-K} \sum_{k=1}^{K} P(X=(t,k))

である。以下、$P(Y=t)>0$の場合を考える。
$N$がそれほど大きくなければ上式をそのまま計算しても良いが、$N$が大きい場合、$N-K項の$和の計算コストが大きい。$N$項の和を回避するために、1人の場合と同様に二項定理を利用して式変形していく。
まず$\frac{k}{k+m}$を適切な形に変形したい。式変形の目標となる適切な形というのは、$m$の依存部分とそうでない部分が積で分離し、$m$の依存部分と$\binom{N-K}{m}$の積について$\sum_{m=0}^{N-K}$の和で二項定理を適用することで$N$相当の項数の和の計算を回避できるような項のたかだか$K$個程度の和の形である。
二項係数の性質から、$0<n<L$の整数$n, L$に対して、

\begin{align}
\binom{L-1}{n} + \binom{L-1}{n-1} &= \frac{(L-1)!}{n!(L-n-1)!} + \frac{(L-1)!}{(n-1)!(L-n)!} \\
&= (L-n) \frac{(L-1)!}{n!(L-n)!} + n\frac{(L-1)!}{n!(L-n)!} \\
&= \frac{L!}{n!(L-n)!} \\
&= \binom{L}{n}
\end{align}

であるので、

\begin{align}
\binom{L-1}{n} &= \binom{L}{n} - \binom{L-1}{n-1} \\
&= \binom{L}{n} - \binom{L}{n - 1} + \binom{L-1}{n-2} \\
&= \binom{L}{n} - \binom{L}{n - 1} + \binom{L}{n-2} - \binom{L-1}{n-3} \\
&\vdots \\
&= \binom{L}{n} - \binom{L}{n - 1} + \binom{L}{n-2} - \binom{L}{n-3} + ... (-1)^{n-1} \binom{L}{1} + (-1)^n \binom{L-1}{0}\\
&= \binom{L}{n} - \binom{L}{n - 1} + \binom{L}{n-2} - \binom{L}{n-3} + ... (-1)^{n-1} \binom{L}{1} + (-1)^n \binom{L}{0}\\
&= \sum_{s=0}^{n} (-1)^{n-s} \binom{L}{s}
\end{align}

と変形できる。途中の変形で$\binom{L-1}{0} = \binom{L}{0} = 1$を使用している。
ここまでの式変形は$n>0$を前提にしていたが、この関係式は$n=0$の場合でも両辺が$1$で成立する。

これを用いて、$L=m+k, n=k-1$の場合で、

\binom{m+k-1}{k-1} = \sum_{s=0}^{k-1} (-1)^{k-s-1} \binom{m+k}{s}

が成り立つ。これをさらに変形していく。
まず、左辺は、

\begin{align}
\binom{m+k-1}{k-1} &= \frac{(m+k-1)!}{(k-1)!m!} \\
&= \frac{k}{k+m} \frac{(m+k)!}{k!m!} \\
\end{align}

と変形できる。
次に右辺について、$\sum_{s=0}^{k-1}$の$s$を$j=k-s$に置き換える。$0 \le s \le k-1$なので、$1 \le j \le k$であり、

\begin{align}
\sum_{s=0}^{k-1} (-1)^{k-s-1} \binom{m+k}{s} &= \sum_{j=1}^{k} (-1)^{j-1} \binom{m+k}{k-j} \\
&= \sum_{j=1}^{k} (-1)^{j-1} \frac{(m+k)!}{(m+j)!(k-j)!}
\end{align}

と変形できる。したがって、

\frac{k}{k+m} \frac{(m+k)!}{k!m!} = \sum_{j=1}^{k} (-1)^{j-1} \frac{(m+k)!}{(m+j)!(k-j)!}

が成り立つので、結果として$\frac{k}{k+m}$は、

\frac{k}{k+m} = \sum_{j=1}^{k} \frac{(-1)^{j-1} m! k!}{(m+j)!(k-j)!}

と変形できる。

これを用いて、

\begin{align}
\frac{k}{k+m}\frac{(N-K)!}{m!(N-K-m)!} &= \sum_{j=1}^{k} \frac{(-1)^{j-1} m! k!}{(m+j)!(k-j)!} \frac{(N-K)!}{m!(N-K-m)!} \\
&= \sum_{j=1}^{k} \frac{(-1)^{j-1} k!(N-K)!}{(k-j)!(m+j)!(N-K-m)!} \\
&= \sum_{j=1}^{k} (-1)^{j-1} \frac{k!}{j!(k-j)!} \frac{j!(N-K)!}{(N-K+j)!} \frac{(N-K+j)!}{(m+j)!(N-K-m)!}\\
&= \sum_{j=1}^{k} (-1)^{j-1} \frac{\binom{k}{j}}{\binom{N-K+j}{j}}\binom{N-K+j}{m+j} \\
\end{align}

であり、二項定理を用いて、

\begin{align}
E_t &= \sum_{k=1}^{K} \sum_{m=0}^{N-K} \frac{k}{k+m} P(X=(t,k)) P(Y=t)^m P(Y>t)^{N-K-m} \frac{(N-K)!}{m!(N-K-m)!} \\
&= \sum_{k=1}^{K} \sum_{m=0}^{N-K} \sum_{j=1}^{k} P(X=(t,k)) P(Y=t)^m P(Y>t)^{N-K-m} (-1)^{j-1} \frac{\binom{k}{j}}{\binom{N-K+j}{j}}\binom{N-K+j}{m+j} \\
&= \sum_{k=1}^{K} P(X=(t,k)) \sum_{j=1}^{k} \frac{(-1)^{j-1} \binom{k}{j}}{P(Y=t)^j \binom{N-K+j}{j}} \sum_{m=0}^{N-K} P(Y=t)^{m+j} P(Y>t)^{N-K-m} \binom{N-K+j}{m+j} \\
&= \sum_{k=1}^{K} P(X=(t,k)) \sum_{j=1}^{k} \frac{(-1)^{j-1} \binom{k}{j}}{P(Y=t)^j \binom{N-K+j}{j}} \left\{ \sum_{m=-j}^{N-K} P(Y=t)^{m+j} P(Y>t)^{N-K-m} \binom{N-K+j}{m+j} - \sum_{m=-j}^{-1} P(Y=t)^{m+j} P(Y>t)^{N-K-m} \dbinom{N-K+j}{m+j} \right\} \\
&= \sum_{k=1}^{K} P(X=(t,k)) \sum_{j=1}^{k} \frac{(-1)^{j-1} \binom{k}{j}}{P(Y=t)^j \binom{N-K+j}{j}} \left\{ P(Y \ge t)^{N-K+j} - \sum_{m=-j}^{-1} P(Y=t)^{m+j} P(Y>t)^{N-K-m} \dbinom{N-K+j}{m+j} \right\} \\
&= \sum_{k=1}^{K} P(X=(t,k)) \sum_{j=1}^{k} \frac{(-1)^{j-1} \binom{k}{j}}{P(Y=t)^j \binom{N-K+j}{j}} \left\{ P(Y \ge t)^{N-K+j} - \sum_{s=0}^{j-1} P(Y=t)^{s} P(Y>t)^{N-K+j-s} \dbinom{N-K+j}{s} \right\} \\
\end{align}

と変形できる。
したがって、時刻$t$で自分が1位になる確率$E_t$は、

E_t = \begin{cases}
P(Y>t)^{N-K} \sum_{k=1}^{K} P(X=(t,k)) & (P(Y=t) = 0) \\
\sum_{k=1}^{K} P(X=(t,k)) \sum_{j=1}^{k} \frac{(-1)^{j-1} \binom{k}{j}}{P(Y=t)^j \binom{N-K+j}{j}} \left\{ P(Y \ge t)^{N-K+j} - \sum_{s=0}^{j-1} P(Y=t)^{s} P(Y>t)^{N-K+j-s} \binom{N-K+j}{s} \right\}  & (P(Y=t) > 0)
\end{cases}

これはたかだか$K^3$項の和で計算されるので$K^2<<N$の状況であれば、$K(N-K)$項の和になる

E_t = \sum_{k=1}^{K} \sum_{m=0}^{N-K} \frac{k}{k+m} P(X=(t,k))P(Y=t)^m P(Y>t)^{N-K-m} \frac{(N-K)!}{m!(N-K-m)!}

を計算するよりも計算コストが小さい。