Yamagishi Complexity Torus Lab | 山岸勇輝ラボ

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

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

@misc{yamagishi2026yoi952,
  author = {Yamagishi, Yuuki},
  title = {Variance Alone Bounds the Chance That Random-Pivot Quicksort Runs Slow, but the Bound Is Far Looser Than Reality},
  year = {2026},
  howpublished = {YOI: https://www.yamagishiyuuki.com/yoi/952},
  note = {Preprint, edition 1}
}

日付の証拠（OpenTimestamps）

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

書誌

要旨

軸を乱数で選ぶクイックソートは平均では速いが、運が悪ければ遅くなりうる。本稿は、比べる回数の平均・分散・三次の積率を漸化式で正確に出し、平均の 1.5 倍や 2 倍を超える確率の上限を分散だけから出して、乱数の試行で実際に超えた割合と比べる。新しい定理も法則も主張しない。

第一に、平均と分散は漸化式で正確に出せ、知られた式と一致する。$n=1000$ で平均 $10985.912663$、分散 $409117.768339$ で、平均は式と相対 $10^{-12}$、分散は式と相対 $10^{-9}$ 以内で一致した。分散を $n$ の二乗で割ると $n=2000$ で $0.414001$ だった（極限 $0.420264$）（第2節）。

第二に、ばらつきの平均に対する割合は n とともに縮む。標準偏差÷平均は $n=100$ で $0.091816$、$1000$ で $0.058222$、$2000$ で $\mathbf{0.052037}$ だった（第2節）。

第三に、分散だけで、遅くなる確率を上から押さえられる。平均の $1.5$ 倍を超える確率は、$n=100$ で $0.032621$ 以下、$1000$ で $0.013378$ 以下、$2000$ で $\mathbf{0.010715}$ 以下で、$2$ 倍を超える確率は $2000$ で $0.002701$ 以下だった（第3節）。

第四に、実際に超える割合は上限をずっと下回る。$n=100$ で $40000$ 回試すと $1.5$ 倍を超えたのは $13$ 回（$0.000325$）で、上限の $\mathbf{0.009963}$ 倍だった。$n=1000$ では $4000$ 回で $0$ 回だった（第3節）。

第五に、分離子は、分散だけで押さえるか、分布の形まで見るかである。分散だけの上限は、同じ分散を持つあらゆる分布に当てはまる最悪の値である。実際の分布は上に長い裾を持つが（歪み $0.867748$）、その裾は分散だけの上限よりずっと薄い（第4節）。

キーワード：クイックソート、比べる回数、分散、カンテリの不等式、裾の確率、乱数の軸

Abstract

Quicksort with a randomly chosen pivot is fast on average, but can be slow with bad luck.This paper computes the mean, variance and third moment of the number of comparisons exactly by recursion, bounds from the variance alone the probability of exceeding one and a half or two times the mean, and compares these with the share that actually exceeds them in random trials.No new theorem or law is claimed.

First, the mean and variance can be computed exactly by recursion and agree with the known formulas: at $n=1000$ the mean was $10985.912663$ and the variance $409117.768339$; the mean matched its formula within a relative $10^{-12}$ and the variance within $10^{-9}$. The variance divided by $n$ squared was $0.414001$ at $n=2000$ (limit $0.420264$) (Section 2).

Second, the spread relative to the mean shrinks with n: standard deviation over mean was $0.091816$ at $n=100$, $0.058222$ at $1000$ and $\mathbf{0.052037}$ at $2000$ (Section 2).

Third, the variance alone bounds the chance of running slow: the probability of exceeding one and a half times the mean was at most $0.032621$ at $n=100$, $0.013378$ at $1000$ and $\mathbf{0.010715}$ at $2000$, and of exceeding twice the mean at most $0.002701$ at $2000$ (Section 3).

Fourth, the share that actually exceeds lies far below the bound: in $40000$ trials at $n=100$, $13$ exceeded one and a half times the mean ($0.000325$), $\mathbf{0.009963}$ of the bound. At $n=1000$, $0$ of $4000$ trials exceeded it (Section 3).

Fifth, the separator is whether one bounds with the variance alone or looks at the shape of the distribution: a bound from the variance alone is the worst case over all distributions with that variance. The actual distribution has a long upper tail (skewness $0.867748$), but that tail is far thinner than the variance-only bound (Section 4).

Keywords: quicksort, number of comparisons, variance, Cantelli’s inequality, tail probability, random pivot

版の記録

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

YOI の一覧へ