2019-06-08

非復元抽出型のクーポンコレクター問題

${ n }$ 種類のアイテムが ${ m }$ コずつ計 ${ N(=nm) }$ コ入ったガチャがある。引いているあいだにアイテムの補充はないとして、すべての種類をコンプリートするまでに引く回数の期待値 ${ E_m(n) }$ を求めましょう。結果は以下のようになります。

$E_m(n)=N(1-\theta)+1$

$\theta^{-1}=(1+\frac{1}{m})(1+\frac{1}{2m})+...+(1+\frac{1}{(n-1)m})$

${ \theta }$ はだいたい、引かずに済むガチャの割合を表しています。

特に ${ m=2 }$ の場合は

$E_2(n)=2n+1-\frac{(2n)!!}{(2n-1)!!}$

とも表せます。

たとえば10種類のアイテムが３つずつ入っている場合は ${ \theta=0.4191... }$ で ${ E_3(10)=18.42.... }$ なので平均して18回程度コンプリートまでに引く必要があります。

Proof

${ p_k }$ で、 ${ k }$ 回目にまだコンプリートできていない確率とすると、包除原理から

${ p_0=1 }$

$p_1=\binom{n}{1}\frac{\binom{N-m}{1}}{\binom{N}{1}}-\binom{n}{2}\frac{\binom{N-2m}{1}}{\binom{N}{1}}+\binom{n}{3}\frac{\binom{N-3m}{1}}{\binom{N}{1}}+...$

$p_2=\binom{n}{1}\frac{\binom{N-m}{2}}{\binom{N}{2}}-\binom{n}{2}\frac{\binom{N-2m}{2}}{\binom{N}{2}}+\binom{n}{3}\frac{\binom{N-3m}{2}}{\binom{N}{2}}+...$

$p_3=\binom{n}{1}\frac{\binom{N-m}{3}}{\binom{N}{3}}-\binom{n}{2}\frac{\binom{N-2m}{3}}{\binom{N}{3}}+\binom{n}{3}\frac{\binom{N-3m}{3}}{\binom{N}{3}}+...$

${... }$

これを縦に集計していくと

$E_m(n)=\sum_{k=0}^\infty p_k$

$=1+\sum_{k=1}^{N-m}\binom{n}{1}\frac{\binom{N-m}{k}}{\binom{N}{k}}-\sum_{k=1}^{N-2m}\binom{n}{2}\frac{\binom{N-2m}{k}}{\binom{N}{k}}+...$

${\displaystyle =1+\sum_{j=1}^{n-1} (-1)^{j-1} \binom{n}{j}\sum_{k=1}^{N-jm} \frac{\binom{N-jm}{k}}{\binom{N}{k}} }$

${\displaystyle \sum_{k=1}^{N-jm} \frac{\binom{N-jm}{k}}{\binom{N}{k}}=\frac{N-jm}{jm+1}=\frac{N+1}{jm+1}-1 }$

なので(※)

${\displaystyle =1+\sum_{j=1}^{n-1} (-1)^{j-1} \binom{n}{j} (\frac{N+1}{jm+1}-1) }$

${\displaystyle =N+1+\sum_{j=0}^{n} (-1)^{j-1} \binom{n}{j}(\frac{N+1}{jm+1}-1) }$

${\displaystyle =N+1+(N+1)\sum_{j=0}^{n} (-1)^{j-1} \binom{n}{j}\frac{1}{jm+1} }$

${\displaystyle =N+1-\frac{N+1}{m}\sum_{j=0}^{n} (-1)^j \binom{n}{j}\frac{1}{j+\frac{1}{m}} }$

soratobipenguin.hatenablog.com

で示した

${\displaystyle \sum_{k=0}^n \frac{(-1)^k {}_nC_k }{k+\alpha} =\frac{n!}{\alpha(\alpha+1)...(\alpha+n)} }$

を適用して

${\displaystyle =N+1-\frac{N+1}{m}\frac{n!}{\frac{1}{m}(1+\frac{1}{m})...(n+\frac{1}{m})} }$

${\displaystyle =N+1-\frac{n!}{\frac{1}{m}(1+\frac{1}{m})...(n-1+\frac{1}{m})} }$

${\displaystyle =N+1-N\frac{(n-1)!}{(1+\frac{1}{m})...(n-1+\frac{1}{m})} }$

より示される。□

(※)正整数 ${ a,b }$ 　 ${ a \gt b }$ に対して

$\sum_{k=1}^{b}\frac{\binom{b}{k}}{\binom{a}{k}}=\frac{b}{a-b+1}$

${ a }$ コの球が袋に入っており、そのうち ${ b }$ コが白玉、残りは赤玉とする。

非復元抽出で袋から球を、赤玉が出るまで引き続ける。それまでに引いた白玉の個数を ${ X }$ とする。

$P(X \ge k)=\frac{\binom{b}{k}}{\binom{a}{k}}$ 　であるから

$E[X]=\sum_{k=1}^b P(X\ge k)=\sum_{k=1}^{b}\frac{\binom{b}{k}}{\binom{a}{k}}$

一方、各白玉ごとにみると、その白玉がどの赤玉よりも先に出る確率は ${ \frac{1}{a-b+1} }$ であり、白玉は ${ b }$ コあるから

$E[X]=\frac{b}{a-b+1}$ □

2019-06-07

重複して集めるクーポンコレクター問題

${ n }$ 種類のアイテム ${ I_1,I_2,...,I_n }$ からなるガチャでどのアイテムも確率 ${ \frac{1}{n} }$ で出現するとする。全てのアイテムを ${ m }$ コずつ重複して集めるまでに引くガチャの回数の期待値 ${ E_m(n) }$ を評価してみましょう。１種類ずつ集める場合の期待値はよく知られていますが、複数ずつ集めるとなると証明の難易度が上がり、結果は以下のようになります。

(Donald J. Newman 1960)

$E_m(n)=n(\log n+(m-1)\log\log n+C_m+o(1))$

定数 ${ C_m }$ は ${ C_m=\gamma-\log (m-1)! }$

のようですが、今回はここまで証明しません。

まず、多項式または級数 ${ f(x_1,...,x_n) }$ について、どの ${ x_i }$ についてみても次数が ${ m }$ 次以上である項を削除した多項式を ${ \{ f(x_1,...,x_n) \} }$ と表わすことにします。

${ k }$ 回目にすべてのアイテムを ${ m }$ 種類ずつ集めていない確率 ${ p_k }$ は

$p_k=\frac{\{ (x_1+...+x_n)^k \}}{n^k}|_{(x_1,...,x_n)=(1,...,1)}$

なので

$E_m(n)=\sum_{k=0}^\infty\frac{\{ (x_1+x_2+...+x_n)^k \} }{n^k}|_{(x_1,...,x_n)=(1,...,1)}$

$S(t)=\sum_{k=0}^{m-1}\frac{t^k}{k!}= \{ e^t \}$

$T(t)=\sum_{k=m}^{\infty}\frac{t^k}{k!}=e^t-\{ e^t \}$

と定義します。もちろん ${ S(t)+T(t)=e^t }$ です。

すぐに分かることとして

(1)

$\{ e^{x_1+x_2+...+x_n} \}=e^{x_1+x_2+...+x_n}-T(x_1)T(x_2)...T(x_n)$

(2)

$\{ e^{x_1+x_2+...+x_n} \}=\sum_{k=0}^\infty \frac{\{(x_1+x_2+...+x_n)^k\}}{k!}$

${ k! }$ が ${ n^k }$ だったら ${ E_m(n) }$ の計算に利用できるので、これを置きかえる工夫をします。利用するのは

${\displaystyle \frac{1}{n^k}=n \int_0^\infty \frac{t^k}{k!}e^{-nt}dt }$

これは部分積分から簡単に確認できます。

$E_m(n)=n\int_0^\infty (1-(T(t)e^{-t})^n)dt$

$\sum_{k=0}^\infty\frac{\{ (x_1+x_2+...+x_n)^k \} }{n^k}$

$=n\sum_{k=0}^\infty \{ (x_1+x_2+...+x_n)^k \} \int_0^\infty \frac{t^k}{k!}e^{-nt}dt$

$=n\int_0^\infty e^{-nt} \sum_{k=0}^\infty \frac{\{ tx_1+tx_2+...+tx_n)^k\}}{k!}dt$

${\displaystyle =n\int_0^\infty e^{-nt} ( e^{t(x_1+...+x_n)}-T(tx_1)...T(tx_n) ) dt }$

$(x_1,...,x_n)=(1,...,1)$ を代入すれば結果が得られる。□

$\frac{E_m(n+1)}{n+1}-\frac{E_m(n)}{n}=\sum_{k=0}^{m-1} \frac{(m-1)!}{(m-k-1)!} \alpha_k(n)$

$=\frac{1}{n+1}+(m-1)\alpha_1(n)+...$

但し $\alpha_k(n)=\int_0^1 \frac{x^n}{t^k}dx$ ,　 $x=T(t)e^{-t}$

$\frac{E_m(n+1)}{n+1}-\frac{E_m(n)}{n}$

$=\int_0^\infty (T(t)e^{-t})^n -(T(t)e^{-t})^{n+1} )dt$

$=\int_0^\infty (T(t)e^{-t})^n S(t)e^{-t} )dt$

$x=T(t)e^{-t}$ と置いて置換積分すると

$dx=(T'(t)-T(t))e^{-t}dt=\frac{t^{m-1}}{(m-1)!}e^{-t}dt$

なので

$=\int_0^1 x^n S(t) \frac{(m-1)!}{t^{m-1}} dx$

$=\sum_{k=0}^{m-1}\int_0^1 \frac{(m-1)!}{k!}\frac{x^n}{t^{m-k-1}} dx$

${\displaystyle =\sum_{k=0}^{m-1} \frac{(m-1)!}{k!} \alpha_{m-k-1}(n) }$

より示される。□

$\sum_{i \lt n} \frac{1}{i+1}=\log n + {\rm Const} +o(1)$

$\sum_{i \lt n} \frac{1}{i \log i}=\log \log n +{\rm Const}+o(1)$

であるからあとは

(1)

$\sum_n \alpha_k(n) \lt \infty$ 　 ${ (1 \lt k \lt m) }$

(2)

$\alpha_1(n)=\frac{1}{n \log n}+\epsilon_n$ 　 $\sum_n|\epsilon_n|\lt \infty$

を示せば目標を達成します。

(1)

$\sum_n \alpha_k(n) =\int_0^1 \frac{dx}{(1-x)t^k}$

であり、発散の可能性は ${ x=0,1 }$ の近傍にある。

${ t \ge 0 }$ において ${ T(t) \le t^m e^t }$ であることが級数展開の係数比較から分かるから ${ x \le t^m }$ つまり ${ x^{\frac{1}{m}}\le t }$

したがって ${ x=0 }$ の近傍では ${ x^{-\frac{k}{m}} }$ のオーダーでおさえられているから発散しない。

一方 ${ x=1 }$ の近傍については、 ${ t \ge 0 }$ において

${ x=1-S(t)e^{-t}\le 1-e^{-t} }$ より

${ t \ge -\log(1-x) }$ であり、

${ k \gt 1 }$ なら $\frac{1}{x (\log x)^k}$ は ${ x=0 }$ の近傍で発散しないことから発散しない。□

(2)

まず ${ \alpha_1(n) }$ を上から評価すると

${ t \ge -\log(1-x) }$ より任意の ${ r \lt n }$ に対して

$t \ge x+\frac{x^2}{2}+...+\frac{x^r}{r}\ge x^r(1+\frac{1}{2}+...+\frac{1}{r}) \ge x^r \log r$

よって

$\alpha_1(n) \le \int_0^1 \frac{x^{n-r}}{\log r}dx=\frac{1}{(n-r+1)\log r}$

なるべく最後の式が小さくなるような ${ r }$ として ${ r=[ \frac{n}{\log n} ] }$ をとると ${ C }$ を定数として

$\alpha_1(n) \le \frac{1}{n\log n}+C \frac{\log\log n}{n (\log n)^2}$

とおさえられる(単純だが計算は少々面倒)。

$\int^\infty\frac{\log\log x}{x (\log x)^2} dx =\int^\infty \frac{\log y}{y^2}dy \lt \infty$

なので ${\displaystyle \sum_n \frac{\log\log n}{n (\log n)^2} }$ は収束する。

次に下から評価する。

${ x_0=T(t_0)e^{-t_0} }$ 　 ${ t_0 \ge 1 }$ として

$\alpha_1(n)\ge \int_0^{x_0}\frac{x^n}{t}dx \ge \frac{1}{t_0}\int_0^{x_0}x^n dx$

$\ge \frac{1}{t_0}(\int_0^1x^n dx-\int_{x_0}^1 dx) =\frac{1}{t_0}(\frac{1}{n+1}-1+x_0)$

${\displaystyle =\frac{1}{t_0}(\frac{1}{n+1}-S(t_0)e^{-t_0}) }$

さらに ${ t \ge 1 }$ であれば

$S(t)\le t^{m-1}(1+...+\frac{1}{(m-1)!})\le et^{m-1}$

であるから

$\alpha_1(n)\ge \frac{1}{(n+1)t_0}-t_0^{m-2}e^{1-t_0}$

${ t_0=\log n+m \log \log n }$ を代入することで ${ C }$ を定数として

$\alpha_1(n) \ge \frac{1}{n\log n}+C \frac{\log\log n}{n (\log n)^2}$

とおさえられる(やはり単純な評価だけど計算は少し面倒)。後は上から評価したときと同様。□

2019-06-05

重複数珠順列の公式

${ r }$ 種類の色( ${ A_1,A_2,...A_r }$ )の玉がそれぞれ ${ a_1,a_2,...,a_r }$ コで計 ${ n }$ コあり、これらを円形に配置する。回転および反転で不変な配置は同一視するとして、その配置の総数を

${ g(n; a_1,a_2,...,a_r) }$

とする。これを計算するための一般的な公式を作ります。

重複円順列の公式が前提となります。記号も引き継ぎます。円順列とみたときの総数は簡単に ${ f }$ と書きます。

soratobipenguin.hatenablog.com

回転対称に関する部分の和は重複円順列の公式をそのまま使えます。

${ n }$ 本の軸を ${ s_1,s_2,...,s_n }$ として ${ s_k }$ に関して対称な配置の総数を ${ S_k }$ とするとバーンサイドの補題から

$g(n; a_1,a_2,...,a_r) =\frac{1}{2n}(\sum_{k=1}^n T_k + \sum_{k=1}^n S_k)$

$=\frac{1}{2}f+\frac{1}{2n}\sum_{k=1}^n S_k$

軸は ${ n }$ が奇数ならすべて玉を一つ通りますが、偶数なら半数は玉を通らず、もう半数は２つの玉を通ります。また、 ${ a_1,a_2,...,a_r}$ の中に奇数がいくつ含まれているかによって線対称な配置の数の計算は変わってきます。このあたりに注意すれば後は単純な重複順列の問題です。

${ a_1,a_2,...,a_r }$ に含まれている奇数の数を ${ d }$ とし、 ${ d }$ のときの

$\frac{1}{n}\sum_{k=1}^n S_k$ を ${ R_d }$ と書くことにすると

${ R_0=\binom{\frac{n}{2}}{ \frac{a_1}{2}, \frac{a_2}{2},...,\frac{a_r}{2} } }$

${ d=1 }$ のとき。唯一の奇数を ${ a_1 }$ とすると

${ R_1=\binom{\frac{n-1}{2}}{ \frac{a_1-1}{2}, \frac{a_2}{2},...,\frac{a_r}{2} } }$

${ d=2 }$ のとき。二つの奇数を ${ a_1,a_2 }$ とすると

${ R_2=\binom{\frac{n}{2}-1}{ \frac{a_1-1}{2}, \frac{a_2-1}{2},\frac{a_3}{2}...,\frac{a_r}{2} } }$

${ d \ge 3 }$ のときは ${ R_d=0 }$

重複数珠順列の公式

上のように定義した ${ R_d }$ によって

${\displaystyle g(n; a_1,a_2,...,a_r) =\frac{1}{2}f+\frac{1}{2}R_d }$

2019-06-04

重複円順列の公式

${ r }$ 種類の色( ${ A_1,A_2,...A_r }$ )の玉がそれぞれ ${ a_1,a_2,...,a_r }$ コで計 ${ n }$ コあり、これらを円形に配置する。回転で不変な配置は同一視するとして、その配置の総数を

${ f(n; a_1,a_2,...,a_r) }$

とする。これを計算するための一般的な公式を作ります。

${ \frac{2k\pi}{n} }$ の時計回りの回転を ${ k }$ 度回転と呼ぶことにします。

バーンサイドの補題を適用すると、 ${ T(k) }$ で ${ k }$ 度回転で不変な配置の総数として

$f(n; a_1,a_2,...,a_r) =\frac{1}{n} \sum_{k=1}^{n} T(k)$

バーンサイドの補題の証明は別の記事で

soratobipenguin.hatenablog.com

${ n }$ の約数 ${ k }$ については、 ${ a_1,a_2,...,a_r }$ の公約数でないときは ${ T(k)=0 }$ であり公約数であるときは

$T(\frac{n}{k})=\binom{\frac{n}{k}}{ \frac{a_1}{k}, \frac{a_2}{k},...,\frac{a_r}{k} }$

${ k }$ 度回転で不変な配置というのは ${ {\rm gcd}(k,n) }$ 度回転で不変な配置と等しいことに注意しましょう。

$\sum_{k=1}^{n}T(k)=\sum_{m|n} T(m)\#\{j; {\rm gcd}(j,n)=m \}$

$=\sum_{m|n} T(m)\phi(\frac{n}{m})=\sum_{k|n} T(\frac{n}{k})\phi(k)$

${ \phi(k) }$ はオイラー関数、つまり ${ k }$ と互いに素な ${ k }$ 以下の正整数の総数です。

以上から

重複円順列の公式

${ C }$ を ${ (n,a_1,a_2,...,a_r) }$ の公約数の集合とすると

$f(n; a_1,a_2,...,a_r)=\frac{1}{n} \sum_{k \in C} \phi(k) \binom{\frac{n}{k}}{ \frac{a_1}{k}, \frac{a_2}{k},...,\frac{a_r}{k} }$

例.　赤玉、青玉、黄玉をそれぞれ４つ、計１２コ円形に並べる場合の総数は

$f(12;4,4,4)=\frac{1}{12} \sum_{k \in \{1,2,4\}} \phi(k) \binom{\frac{12}{k}}{ \frac{4}{k}, \frac{4}{k},\frac{4}{k} }=2896$

2019-06-04

指数分布の最大値分布(改)

soratobipenguin.hatenablog.com

と後半は同じですが前半のモーメントの計算はずっと簡単になったので書き直しました。パラメータの異なる独立した指数分布の和の形にしてしまいます。

${X_1,X_2,..,X_n \sim {\rm Exp}(\lambda)}$ 互いに独立

${Y=\max (X_1,X_2,..,X_n)}$

このとき ${Y}$ の分布について考えてみる。

${ X'_k \sim {\rm Exp} (k \lambda) }$ 　 ${ 1 \le k \le n }$ 　互いに独立

とする。このとき

$Y$ 　と　 $Z=\sum_{k=1}^n X'_k$ 　は分布として等しい

特性関数が等しいことを示す。

$\phi_Z(u)=\prod_{k=1}^n \phi_{X'_k}(u)=\prod_{k=1}^n \frac{1}{1-\frac{iu}{k \lambda}}$

一方

$P(Y \le x)=\prod_{k=1}^n P(X_k \le x)=(1-e^{-\lambda x})^n$

なので ${ Y }$ の密度関数は微分して

$f_Y(x)=n \lambda e^{-\lambda x} (1-e^{-\lambda x})^{n-1}$

よって特性関数は

$\phi_Y(u)=n \lambda \int_0^{\infty} e^{-\lambda x} (1-e^{-\lambda x})^{n-1} e^{iux}$

$=n \lambda \sum_{k=0}^{n-1} \int_0^\infty \binom{n-1}{k}(-1)^k e^{-(\lambda k+\lambda-iu)} dx$

$=n \sum_{k=0}^{n-1} \binom{n-1}{k}\frac{(-1)^k}{k+1 -\frac{iu}{\lambda}}$

ここで

soratobipenguin.hatenablog.com

で示した

${\displaystyle \sum_{k=0}^n \frac{(-1)^k {}_nC_k }{k+\alpha} =\frac{n!}{\alpha(\alpha+1)...(\alpha+n)} }$

により

$=n! \prod_{k=1}^n \frac{1}{ k-\frac{iu}{\lambda}}$

$= \prod_{k=1}^n \frac{1}{ 1-\frac{iu}{k\lambda}}$ □

モーメントの計算は ${ Y }$ より ${ Z }$ の方がずっと容易である。

$E[Z]=\sum_{k=1}^n E[X'] =\frac{1}{\lambda k}$

${\rm Var}(Z)=(\sum_{k=1}^n (X'_k-E[X_k]))^2$

${\displaystyle =\sum_{k=1}^n (X'_k-E[X'])^2 =\sum_{k=1}^n {\rm Var}(X_k)=\sum_{k=1}^n\frac{1}{(\lambda k)^2} }$

今度は ${n}$ が大きくなる時に ${ Y }$ が近づいていく分布を求める。 ${ n }$ を動かすので ${ Y }$ は ${ Y_n }$ と書くことにする。

$Y_n-\lambda^{-1} \log n \rightarrow ^d W 　(n \rightarrow \infty)$

但し ${W}$ の分布関数 ${G}$ は

${\displaystyle G(x)= \exp(-e^{-\lambda x })}$

${W_n=Y_n-\lambda^{-1} \log n}$ の分布関数を ${G_n}$ とする。

${F_n(x)=(1-e^{- \lambda x})^n　\chi_ { [ 0,\infty )}(x) }$

${\chi}$ は定義関数。

${G_n(x)=F_n(x+\lambda^{-1} \log n)}$

${=(1-\frac{e^{-\lambda x}}{n})^n \chi_{ [-\lambda^{-1} \log n,\infty)}(x) }$

これは　 ${ n \rightarrow \infty }$ によって任意の実数 ${x}$ で

${G(x)= \exp(-e^{-\lambda x}) }$ に収束する。□

${ G(x) }$ はガンベル分布と呼ばれ、極値分布の一つです。

${E[W],{\rm Var}(W)}$ を計算してみると

${E[ W_n ] \rightarrow E[W] }$ が比較的容易に分かるので

$E[W]=\lim_{n \rightarrow \infty }(E [ Y_n ] -\lambda^{-1} \log n)$

$=\lambda^{-1} \lim_{n \rightarrow \infty } (\sum_{k=1}^n \frac{1}{k}-\log n)$

${\displaystyle=\gamma} \lambda^{-1}$

となる（ ${ \gamma}$ はオイラー定数）。

同じようにして

${\rm Var}(W)=\lambda^{-2} \sum_{k=1}^\infty \frac{1}{k^2}= \frac{\pi^2}{6}\lambda^{-2}$

おまけとして3次４次の中心化モーメントを記しておくと

$E[ (W-\gamma \lambda^{-1})^3 ]=2 \zeta(3) \lambda^{-3}$

$E[ (W-\gamma \lambda^{-1})^4 ]=6\lambda^{-4} \zeta(4)+3\lambda^{-4} \zeta(2)^2=\frac{3\pi^4}{20} \lambda^{-4}$

2019-06-02

不均等な場合のクーポンコレクター問題

${ n }$ 種類のアイテム ${ I_1,I_2,...,I_n }$ からなるガチャで ${ I_k }$ が当たる正の確率を ${ p_k }$ とする( $\sum_{k=1}^n p_k=1$ )。

このガチャについて全種類コンプリートするまでに引くガチャの回数の期待値 ${ E }$ は

${ J:=\{ I_1,I_2,...,I_n \} }$

${ J }$ の空でない部分集合 ${ L }$ に対して ${ S(L) }$ をそのアイテムに対応する確率の和とすると(例. ${ S(\{ I_1,I_2 \}) =p_1+p_2 }$ )

$E=\sum_{L\subset J, L \neq \emptyset } \frac{(-1)^{\#L-1}}{S(L)}$

3種類の場合を見れば一般の場合も計算方法は全くかわらないので、見た目の煩雑さを避けるために ${ n=3 }$ の場合の証明をみる。書き下すと、３種類のアイテム ${ I_1,I_2,I_3 }$ の出現確率がそれぞれ ${ p,q,r }$ であるとすると

$E=\frac{1}{p}+\frac{1}{q}+\frac{1}{r}-\frac{1}{p+q}-\frac{1}{q+r}-\frac{1}{r+p}+1$

コンプリート達成時の回数を ${ T }$ とする。 ${ t }$ 回目にコンプリートしていないことは ${ T \gt t }$ と表される。 ${ t }$ 回目までにアイテム ${ I_k }$ がまだ出現していない事象を ${ R_i }$ とすると

$P(T \gt t )=P(R_1 \cup R_2 \cup R_3)$

包除原理から

${\displaystyle =P(R_1)+P(R_2)+P(R_3)}$

${\displaystyle -P(R_1 \cap R_2)-P(R_2 \cap R_3)-P(R_3 \cap R_1)}$

${\displaystyle +P(R_1 \cap R_2 \cap R_3 ) }$

たとえば ${ P(R_1) }$ は ${ t }$ 回ずっとアイテム ${ I_1 }$ が出ない確率であるから ${ (1-p)^t }$ と計算できる。他も同様。

${P(R_1 \cap R_2 \cap R_3 ) }$ は ${ t=0 }$ でのみ ${ 1 }$ で、それ以外は ${ 0 }$ であることに注意する。

以上から ${ 0^0=1 }$ として

$P(T \gt t)=(1-p)^t+(1-q)^t+(1-r)^t$

$-(1-p-q)^t-(1-q-r)^t-(1-r-p)^t+0^t$

非負整数値をとる確率変数の期待値計算の便利な公式

$E[T]=\sum_{t=0}^\infty P(T \gt t)$

より計算が完了する。□

2019-06-01

円周率の無理数性(ニーベンの証明をなるべく入りやすい順序で)

${ \pi }$ が正整数 ${ a,b }$ によって ${ \pi=\frac{a}{b} }$ と表されたと仮定する。

${ 2n }$ 次多項式 ${ f_n }$ を

$f_n(x)=\frac{x^n(a-bx)^n}{n!}$ 　と定義する。

すると以下が成り立つ。

(1)任意の正整数 ${ n }$ に対して

$\int_0^\pi f_n(x)\sin x dx$ 　は整数である。

(2)十分大きな正整数 ${ n }$ に対して

$\int_0^\pi f_n(x)\sin x dx$ 　は整数でない。

よって矛盾が生じ、 ${ \pi }$ の無理数性が証明される。

簡単な(2)を先に片づけておこう。

${0 \lt x \lt \pi }$ 　で

$\displaystyle {0 \lt f_n(x)\sin x \lt \frac{\pi^n a^n}{n!} }$

なので

${\displaystyle0 \lt \int_0^\pi f_n(x)\sin x dx \lt \frac{\pi^{n+1} a^n}{n!} }$

${\displaystyle \frac{\pi^{n+1} a^n}{n!} }$ は ${ n \rightarrow \infty }$ で ${ 0 }$ に収束するから十分大きな ${ n }$ では ${ 1 }$ 未満の正数であり、整数でない。□

メインの(1)へ進もう。

$\int_0^\pi f_n(x)\sin x dx$ は ${ f_n(x) }$ が多項式であることから ${ f_n }を微分側にして$ 部分積分を何度も( ${ 2n }$ 回)繰り返せば積分なしに表せることに注意しよう。

二度部分積分すると

${\displaystyle　\displaystyle \int_0^\pi f_n(x)\sin x dx =f_n(0)+f_n(\pi)- \int_0^\pi f''_n(x)\sin x dx }$

となる。これを繰りかえしていけば

${\displaystyle \int_0^\pi f_n(x)\sin x dx =\sum_{k=0}^n (-1)^k(f_n^{(2k)}(0)+f_n^{(2k)}(\pi))　 }$

となる。

よってこれが整数であることを示すには

${0 \le k \le 2n}$ のとき

${ f_n^{(k)}(0), f_n^{(k)}(\pi) }$ 　は整数である

ことを示せばよい。

先に ${ f_n^{(k)}(0) }$ が整数であることを示す。

ライプニッツの公式から

$f_n^{(k)}(x)=\frac{1}{n!}\sum_{i=0}^k \binom{k}{i}(x^n)^{(i)}((a-bx)^n)^{(k-i)}$

だが

${ (x^n)^{(i)} }$ に ${ 0 }$ を代入して ${ 0 }$ とならないのは ${ i=n }$ の時だけなので ${ k \lt n }$ なら当然 ${ f_n^{(k)}(0)=0 }$ であり ${ k \ge n }$ なら

${\displaystyle f_n^{(k)}(0)=\binom{k}{n}\frac{n!}{(2n-k)!}a^{2n-k}(-b)^{k-n} }$

これは整数である。

さらに ${ f_n(\pi-x)=f_n(x) }$ であるから

${ f_n^{(k)}(\pi-x)=(-1)^k f_n^{(k)}(x) }$

${ f_n^{(k)}(\pi)=(-1)^k f_n^{(k)}(0) }$

よって ${ f_n^{(k)}(\pi)}$ も整数となる。　□

数酸

数学に関して書き留めておこうと思ったものを気まぐれに。

非復元抽出型のクーポンコレクター問題

重複して集めるクーポンコレクター問題

重複数珠順列の公式

重複円順列の公式

指数分布の最大値分布(改)

不均等な場合のクーポンコレクター問題

円周率の無理数性(ニーベンの証明をなるべく入りやすい順序で)