今回扱うのはAdvent Calendar Contest 2023 N問題 No.2586 Yet Another Sugoroku Problemです。公式解説はシュトルツ・チェザロの定理を用いて解を求めていますが、実はもっと初等的に解を求められるのでその解説をしてみます。

問題の概要

正確な問題文はこちらです。

正整数$N$が与えられます。正整数$m$に対し、出た目の和が$m$以上となるまで$N$面サイコロを振るという試行を$P(m)$と置き、$P(m)$においてサイコロを振る回数の期待値を$f(m)$と置きます。

\[ \lim_{m \to \infty} \frac{f(m)}{m} \]

を求めてください。

前置き

サイコロを$1$回振った時の出目の期待値は、$1,\ldots,N$の平均値である$\frac{N+1}{2}$です。ということは、$m$以上になるまでの平均回数$f(m)$はおよそ$\frac{2m}{N+1}$になることが予想できます。ということは、答えが$\frac{2}{N+1}$になりそうですね。これを真面目に検証してみましょう。

解説

$m$を正整数とします。$P(m)$において出目のなす数列としてありえる数列全体の集合を$S_m$と置きます。各$s \in S_m$に対し$s$の長さを$\ell(s)$と置き、$s$の成分の総和を$\lvert s \rvert$と置き、$P(m)$において出目のなす数列が$s$となる確率を$p(s)$と置きます。

次の補題が鍵となります。

補題

サイコロを$1$回振った時の出目の期待値$\frac{N+1}{2}$と$P(m)$においてサイコロを振る回数の期待値$f(m)$の積は$P(m)$における出目の総和の期待値と等しい。すなわち

\[ \frac{N+1}{2} f(m) = \sum_{s \in S_m} p(s) \lvert s \rvert \]

である。

一見直感的に当たり前のようですが、期待値の定義に従って示してみましょう。

証明

$s \in S_m$と$\ell(s)$以下の正整数$i$に対し、$s$の$i$個目の成分を$s_i$と書き表す。$m$以下の任意の正整数$i$に対し、$i$回目にサイコロを振った時の出目の全事象内における期待値は$\frac{N+1}{2}$なので、

\[ \frac{\displaystyle\sum_{s \in S_m \land \ell(s) \geq i} p(s) s_i}{\displaystyle\sum_{s \in S_m \land \ell(s) \geq i} p(s)} = \frac{N+1}{2} \]

である。従って、

\[ \begin{array}{rcl} \displaystyle\sum_{s \in S_m} p(s) \lvert s \rvert &\displaystyle = &\displaystyle \sum_{s \in S_m} p(s) \sum_{i=1}^{\ell(s)} s_i \\
&\displaystyle = &\displaystyle \sum_{i=1}^{m} \sum_{s \in S_m \land \ell(s) \geq i} p(s) s_i \\
&\displaystyle = &\displaystyle \sum_{i=1}^{m} \left( \sum_{s \in S_m \land \ell(s) \geq i} p(s) \right) \frac{N+1}{2} \\
&\displaystyle = &\displaystyle \frac{N+1}{2} \sum_{i=1}^{m} \sum_{s \in S_m \land \ell(s) \geq i} p(s) \\
&\displaystyle = &\displaystyle \frac{N+1}{2} \sum_{s \in S_m} \sum_{i=1}^{\ell(s)} p(s) \\
&\displaystyle = &\displaystyle \frac{N+1}{2} \sum_{s \in S_m} p(s) \ell(s) \\
&\displaystyle = &\displaystyle \frac{N+1}{2} f(m) \end{array} \]

である。$\Box$

それでは本題に戻りましょう。$S_m$の定義から任意の$s \in S_m$に対し$m \leq \lvert s \rvert < m + N$であるので、

\[ m = \sum_{s \in S_m} p(s) m \leq \sum_{s \in S_m} p(s) \lvert s \rvert < \sum_{s \in S_m} p(s)(m + N) = m + N \]

と評価できます。従って、補題より

\[ m \leq \frac{N+1}{2} f(m) < m + N \]

となります。両辺を$\frac{2}{(N+1)m}$倍し

\[ \frac{2}{N+1} \leq \frac{f(m)}{m} < \frac{2}{N+1} \left( 1 + \frac{N}{m} \right) \stackrel{m \to \infty}{\longrightarrow} \frac{2}{N+1} \]

となるので、挟み撃ちの原理より

\[ \lim_{m \to \infty} \frac{f(m)}{m} = \frac{2}{N+1} \]

となります。これにてこの問題が解けました。

自分用覚え書き

github pagesで数式を使う際は、閉じカッコと半角アンダーバーの間に半角スラッシュを入れないとmarkdownからhtmlへの翻訳の仕様でバグるらしい。

数式環境をくくる大括弧と数式環境内の中括弧や半角空白は半角スラッシュ２つ、改行は半角スラッシュ５つ、その他は基本的に半角スラッシュ１つで良さそう。htmlとmathjaxの関係が難しい。

arrayとalignはどちらも使える。arrayが使えない気がしてしまったのは中括弧につける半角スラッシュの個数を間違えていたから。alignはアンパサンドを等号の右側につけて半角空白を２つ入れると幅がちょうど良さそう。arrayなしだとアンパサンドは使えない。