Yamagishi Complexity Torus Lab | 山岸勇輝ラボ

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

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

@misc{yamagishi2026yoi844,
  author = {Yamagishi, Yuuki},
  title = {“Always Terminates” and “Always Correct” Cannot Be Traded for Each Other},
  year = {2026},
  howpublished = {YOI: https://www.yamagishiyuuki.com/yoi/844},
  note = {Preprint, edition 1}
}

日付の証拠（OpenTimestamps）

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

書誌

要旨

乱数を使う手順は「速い」とだけ言われがちである。本稿は、そこに二つの型があり、取り替えられないことを数える。新しい定理も法則も主張しない。

第一に、誤りは片側にしか出ない。等しい行列を $4000$ 回試して、「違う」と言った回数は $0$ である（第2節）。

第二に、違う行列は見逃すことがある。$1$ 回では $\mathbf{0.510250}$、$5$ 回でも $\mathbf{0.027000}$ の割合で見逃す（第2節）。

第三に、その上限はちょうど達成される。法 $2$ では見逃しが $2^{-k}$ と標本誤差の範囲で一致し、下回らない（第2節）。

第四に、法を大きくすると下がる。$1$ 回あたりの見逃しは法 $2$ で $0.500500$、法 $11$ で $\mathbf{0.083750}$ である（第2節）。

第五に、これが本稿の芯である。必ず正しくしようとすると、終わりが読めなくなる。証拠が出るまで引くと平均 $\mathbf{1.942000}$ 回だが最大 $15$ 回まで伸び、等しい側では $500$ 回引いても出ない（第3節）。

第六に、分離子は、間違いの確率を問うか、終わるまでの回数を問うかである。同じ一回の操作から、二つの別の約束が作れる（第4節）。

キーワード：乱択、片側誤り、モンテカルロ、ラスベガス、見逃し、模型

Abstract

Procedures that use randomness are usually just called “fast”.This paper counts that there are two kinds, and that they cannot be traded for each other.No new theorem or law is claimed.

First, the error falls on one side only: over $4000$ equal pairs, “unequal” was said $0$ times (Section 2).

Second, unequal pairs can be missed: one round misses with a share of $\mathbf{0.510250}$, and five rounds still with $\mathbf{0.027000}$ (Section 2).

Third, the bound is exactly attained: over the field of two the misses match $2^{-k}$ within sampling error and do not fall below it (Section 2).

Fourth, a larger modulus lowers it: one round misses with $0.500500$ modulo $2$ and $\mathbf{0.083750}$ modulo $11$ (Section 2).

Fifth, and this is the core. Making it always correct makes the stopping time unreadable: drawing until a witness averages $\mathbf{1.942000}$ rounds but reaches $15$, and on an equal pair nothing appears in $500$ draws (Section 3).

Sixth, the separator is whether one asks about the probability of error or about the number of rounds until it stops: one and the same operation yields two different promises (Section 4).

Keywords: randomised algorithm, one-sided error, Monte Carlo, Las Vegas, miss rate, model

版の記録

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

YOI の一覧へ