Yamagishi Complexity Torus Lab | 山岸勇輝ラボ

要旨

乱数の軸で遅くなる確率は分散だけで上から押さえられるが、その上限は実際よりずっと甘い（論文952）。そこでは、分布の形を使った指数の裾の上限は名前を挙げるにとどめた。本稿は、952 の乱数の軸のクイックソートの比べる回数について、積率母関数を漸化式で出してチェルノフの上限を作り、952 のカンテリの上限と、$n=100$ の厳密な分布の裾と比べる。新しい定理も法則も主張しない。

第一に、裾の遠くでは、積率母関数の上限が桁違いに締まる。$n=100$ で平均の 2 倍を超える確率は厳密に $4.780561$×10⁻⁹ で、チェルノフの上限はその $\mathbf{20.97568}$ 倍、カンテリの上限は $\mathbf{1.748705}$×10⁶ 倍だった（第3節）。

第二に、平均に近い外れでは、分散だけの上限のほうが締まる。平均の 1.25 倍を超える確率（厳密 $1.525455$×10⁻²）では、カンテリ $1.188529$×10⁻¹ がチェルノフ $1.265041$×10⁻¹ より小さかった（第3節）。

第三に、二つの上限が入れ替わる点は $n$ で動く。$n=100$ では平均の $\mathbf{1.2598}$ 倍、$n=1000$ では $1.1599$ 倍を超える確率で二つが等しくなり、それより遠い裾ではチェルノフが小さかった（第4節）。

第四に、$n=1000$ では差がさらに開く。平均の 2 倍を超える確率の上限は、カンテリ $3.378363$×10⁻³ に対してチェルノフ $9.840440$×10⁻¹⁴ だった（第4節）。

第五に、分離子は、外れを平均の何倍で測るか、標準偏差の何倍で測るか。入れ替わる外れを平均で割ると $n=100$ と $n=1000$ の比は $1.6251$ だが、標準偏差で割ると $\mathbf{2.8299}$ 倍と $2.7462$ 倍で比は $1.0305$ だった（第5節）。

キーワード：クイックソート、チェルノフの上限、積率母関数、カンテリの不等式、裾の確率、標準偏差。

射程（何を示さないか）

新しい定理も法則も主張しない。積率母関数から裾の確率の上限を作るチェルノフの方法、乱数の軸のクイックソートの比べる回数が平均から大きく外れる確率の大きさが調べられていること（マクダーミドとヘイワード）、分散だけの上限は遠い裾で甘いことは、いずれも確率論とアルゴリズムの解析で既知である。比べる回数だけを数える。記憶の読み書き、定数倍、再帰の深さは扱わない（論文927・952 と同じ）。上限を二つに限る。チェルノフとカンテリの二つだけを比べ、ほかの不等式や最良の上限は扱わない。$n$ は 100 と 1000 だけで、$n$ を限りなく大きくしたときの裾の形は主張しない。入れ替わりを広げない。二つの上限が入れ替わる外れが標準偏差の何倍かは、この二つの $n$ の値で、ほかのアルゴリズムや分布でも同じとは言わない。既刊との関係：論文952 の射程注記は、強い上限を導かず、分布の形を使った指数の裾の上限は名前を挙げるにとどめ、分散だけの上限を出すと書いた。本稿はその席に座る（先客なし）。論文952 は、乱数の軸で遅くなる確率は分散だけで上から押さえられるが、その上限は実際よりずっと甘いことを示した。ここでは、分布の形まで使った上限がどれだけ締まり、どこで分散だけの上限に負けるかを数える。加えたのは、積率母関数を漸化式で出しチェルノフの上限を作ったこと、$n=100$ の厳密な分布を畳み込みで出し二つの上限と比べたこと、二つの上限が入れ替わる点を出したこと、その点を平均と標準偏差の二つの目盛りで比べたこと、分離子を「平均の何倍か、標準偏差の何倍か」に置いたことである。

1. 記法と問い

設定：論文952 と同じく、長さ $n$ の列を軸を一様な乱数で選ぶクイックソートで並べ、比べる回数を $C_n$ とする。軸が $K$ 番目のとき $C_n=(n-1)+C_{K-1}+C’_{n-K}$（二つは独立）なので、積率母関数 $M_n(\lambda)=\mathrm{E} e^{\lambda C_n}$ は

$$M_n(\lambda)=e^{\lambda(n-1)}\,\frac{1}{n}\sum_{K=1}^{n}M_{K-1}(\lambda)\,M_{n-K}(\lambda),\qquad M_0=M_1=1$$

を満たす。これを対数で $n$ まで回し、平均を $\mu$ として、チェルノフの上限とカンテリの上限（論文952）

$$P(C_n\ge\mu+t)\le\min_{\lambda>0}M_n(\lambda)\,e^{-\lambda(\mu+t)},\qquad P(C_n-\mu\ge t)\le\frac{\sigma^2}{\sigma^2+t^2}$$

を比べる。$\lambda$ は $10^{-5}$〜$2$ の対数で等間隔の 80 点から最小の近くを選び、三分探索で詰めた。$n=100$ では、$C_n$ の分布そのものを同じ漸化式の畳み込みで出した（確率の和 $1.000000000000$・0.2 秒）。

問い：分布の形を使った上限は、分散だけの上限よりどれだけ締まり、どこで負けるか。

2. 平均と分散

計算 2.1：$n=100$ で平均 $647.850259$・分散 $3538.266678$（厳密な分布から出した値も同じ）、$n=1000$ で平均 $10985.912663$・分散 $409117.768339$。積率母関数の対数の $\lambda=0$ での傾きは、$n=100$ で $647.8503$、$n=1000$ で $10985.9126$ で、平均と相対 $10^{-4}$ 以内で一致した。

3. $n=100$ の三つの値

計算 3.1：平均の何倍かを超える確率。

三つのどれでも、二つの上限は厳密な値以上だった。チェルノフの最小を与えた $\lambda$ は $2.032720$×10⁻²・$2.719945$×10⁻²・$3.474357$×10⁻² だった。

観察 3.2　遠い裾ではチェルノフが、近い外れではカンテリが締まった。カンテリ÷厳密は $7.791305$ から $1.748705$×10⁶ に広がり、チェルノフ÷厳密は $8.292877$ から $20.97568$ にしか広がらなかった。平均の 1.25 倍では、カンテリのほうがチェルノフより小さかった。

4. 入れ替わりと $n=1000$

計算 4.1：$n=1000$ の二つの上限。

計算 4.2：二つの上限が等しくなる点を二分法で出すと、$n=100$ で平均の $1.2598$ 倍、$n=1000$ で $1.1599$ 倍で、それより平均に近いとカンテリが、遠いとチェルノフが小さかった。

5. 分離子

観察 5.1　分離子は、外れを平均の何倍で測るか、標準偏差の何倍で測るか。入れ替わる点の外れを標準偏差で割ると、$n=100$ で $2.8299$ 倍、$n=1000$ で $2.7462$ 倍で、$n=100$÷$n=1000$ の比は $1.0305$ だった。平均で割った値の比は $1.6251$ だった。同じ「平均の 2 倍」は、$n=100$ で標準偏差の $10.8913$ 倍、$n=1000$ で $17.1756$ 倍の外れで、$n$ が大きいほど遠い裾になる。$n=1000$ では平均の 1.25 倍がすでに標準偏差の $4.2939$ 倍で、入れ替わりの $2.7462$ 倍より遠く、三つともチェルノフが小さかった。

観察 5.2　言わないこと。$n$ を限りなく大きくしたときの裾の形、ほかの不等式や最良の上限、入れ替わりの倍率がほかのアルゴリズムでも同じかどうか、実際の時間は扱わない。示したのは、二つの $n$ で、分布の形を使った上限と分散だけの上限がどこで入れ替わり、遠い裾でどれだけ差が開くかである。

6. 点呼と結び

1. 積率母関数の漸化式（第1節）：傾きは平均と一致。
2. 平均の 2 倍でチェルノフは厳密の $\mathbf{20.97568}$ 倍（計算 3.1）：カンテリは $\mathbf{1.748705}$×10⁶ 倍。
3. 平均の 1.25 倍ではカンテリが小さい（計算 3.1）：近い外れは分散だけが締まる。
4. 入れ替わりは平均の $\mathbf{1.2598}$ 倍と 1.1599 倍（計算 4.2）：$n$ で動く。
5. 標準偏差では $\mathbf{2.8299}$ 倍と 2.7462 倍・比 1.0305（観察 5.1）：そろう。
6. 平均の何倍か、標準偏差の何倍か（観察 5.1）：分離子・論文952 の射程注記。

結び：遅くなる確率の上限は、裾の遠くでは積率母関数が、近くでは分散だけが締まる。952 のクイックソートで積率母関数を漸化式で出すと、$n=100$ で平均の 2 倍を超える確率のチェルノフの上限は厳密な値の $20.97568$ 倍で、カンテリの上限の $1.748705$×10⁶ 倍よりずっと締まったが、平均の 1.25 倍ではカンテリのほうが小さかった。二つは平均の $1.2598$ 倍（$n=1000$ で $1.1599$ 倍）で入れ替わり、その外れは標準偏差の $2.8299$ 倍と $2.7462$ 倍だった。分離子は、外れを平均の何倍で測るか、標準偏差の何倍で測るか。既刊との位置：論文952 が分散だけで押さえた裾に、論文952 が名前を挙げるにとどめた分布の形を使う上限を足した。正直に言えば、二つの $n$ で二つの上限と厳密な値を並べた。分布の形を使うとどこから得をするか、そこまでである。

参考文献

1. Chernoff, H. (1952). A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Annals of Mathematical Statistics.
2. McDiarmid, C., & Hayward, R. (1996). Large deviations for Quicksort. Journal of Algorithms.
3. 山岸勇輝 (2026). 『先頭を軸にするクイックソートは整った入力で最も遅く、軸を乱数で選ぶと平均の遅さは入力によらなくなる』[論文927]. YOI: https://www.yamagishiyuuki.com/yoi/927
4. 山岸勇輝 (2026). 『乱数の軸で遅くなる確率は分散だけで上から押さえられるが、その上限は実際よりずっと甘い』[論文952]. YOI: https://www.yamagishiyuuki.com/yoi/952

作成にあたって：本稿の着想と内容は、著者自身の考察に基づくものです。文章の構成整理や英訳、数式の確認には AI（大規模言語モデル）の助力を得ました。最終的な内容の解釈や誤りがあれば、それらはすべて著者の責に帰します。お気づきの点があれば、ご教示いただければ幸いです。

書誌

山岸勇輝（2026）「遅くなる確率の上限は、裾の遠くでは積率母関数が、近くでは分散だけが締まる」［論文987］. YOI: https://www.yamagishiyuuki.com/yoi/987

@misc{yamagishi2026yoi987,
  author = {Yamagishi, Yuuki},
  title = {Far in the Tail the Moment Generating Function Bounds a Slow Sort Tighter; Near the Mean Variance Alone Does},
  year = {2026},
  howpublished = {YOI: https://www.yamagishiyuuki.com/yoi/987},
  note = {Preprint, edition 1}
}