Yamagishi Complexity Torus Lab | 山岸勇輝ラボ

論文987 の記録のページです。住所（YOI）は https://www.yamagishiyuuki.com/yoi/987 で、論文の本文は下の PDF にあります。ファイルは自分で用意した置き場所（https://yamagishi.sakuraweb.com）に置き、日付の証拠（.ots）を添えています。

本文はサイトの記事でも読めます（2026年10月17日 12:20 に公開します）。

@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}
}

日付の証拠（OpenTimestamps）

2026年10月1日に、2 本の PDF の指紋（SHA-256）をまとめて OpenTimestamps に送り、ビットコインのブロック 969451・969456・969461・969490 に記録されました（2026年10月01日 23:00（日本時間））。この .ots があれば、PDF がその時点で存在したことを、このサイトや運営者を信用しなくても、誰でも確かめられます。

書誌

要旨

乱数の軸で遅くなる確率は分散だけで上から押さえられるが、その上限は実際よりずっと甘い（論文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節）。

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

Abstract

Variance alone bounds the chance that random-pivot quicksort runs slow, but the bound is far looser than reality (Paper 952). Exponential tail bounds using the shape of the distribution were only named there.For the number of comparisons of the random-pivot quicksort of Paper 952, this paper builds the Chernoff bound from a recursion for the moment generating function and compares it with the Cantelli bound of Paper 952 and with the exact tail of the distribution at $n=100$.No new theorem or law is claimed.

First, far in the tail, the bound from the moment generating function is tighter by orders of magnitude: for $n=100$ the chance of exceeding twice the mean is exactly $4.780561$×10⁻⁹; the Chernoff bound was $\mathbf{20.97568}$ times that and the Cantelli bound $\mathbf{1.748705}$×10⁶ times (Section 3).

Second, for departures near the mean, the variance-only bound is tighter: for exceeding 1.25 times the mean (exactly $1.525455$×10⁻²), Cantelli’s $1.188529$×10⁻¹ was smaller than Chernoff’s $1.265041$×10⁻¹ (Section 3).

Third, where the two bounds cross moves with $n$: the two were equal for exceeding $\mathbf{1.2598}$ times the mean at $n=100$ and $1.1599$ times at $n=1000$, with Chernoff smaller further out (Section 4).

Fourth, at $n=1000$ the gap widens further: for exceeding twice the mean the bounds were $3.378363$×10⁻³ for Cantelli and $9.840440$×10⁻¹⁴ for Chernoff (Section 4).

Fifth, the separator is whether a departure is measured in multiples of the mean or of the standard deviation: dividing the crossing departure by the mean gave a ratio of $1.6251$ between $n=100$ and $n=1000$, but dividing by the standard deviation gave $\mathbf{2.8299}$ and $2.7462$, a ratio of $1.0305$ (Section 5).

Keywords: quicksort, Chernoff bound, moment generating function, Cantelli’s inequality, tail probability, standard deviation

版の記録

ここの PDF（倉庫の v1）は第1版（2026年9月）の原稿から作りました。ファイルは版ごとに分けて置いています（/yoi/987/v1/ の下）。中身を直すときは、このファイルを書き換えず、新しい版を足します（住所 https://www.yamagishiyuuki.com/yoi/987 はいつも最新の版を指します）。

YOI の一覧へ