情報科学 › LLM アーキテクチャ › 推論

累積和による標本抽出の正しさ

命題 6.1（「推論」§6）・ ✓公理まで証明済み

$q$ を $V = \{1, \ldots, N\}$ 上の確率分布、 $C_j = \sum_{i \le j} q_i$ （ $C_0 = 0$ 、 $C_N = 1$ ）とします。 $U$ を区間 $(0, 1)$ 上の一様分布に従う確率変数とし、

X = \min\{ j \in V : C_j \ge U \}

とおくと、すべての $j$ で $P(X = j) = q_j$ です。計算に必要な比較と加算は $O(N)$ 回です。

本文で読む（証明と前後の説明）→

閉包の状態

✓ 公理まで証明済み

証明が使う定理を前提としてたどると、Rikai の中の証明だけで定義・公理（物理では基本仮定）までつながっています（前提の定理類 5 件、定義なども含めて 7 件）。

印の意味: ✓公理まで証明済み・ △証明あり（閉包未完）・ ※主張のみ。テーマごとの集計は閉包の状況。

前提をたどる証明が使う定理・定義（直接 2 件）

▸ を開くと、その項目の証明が使う前提が出ます。深い先は各項目のページでたどれます。

逆関数法✓定理 3.3・分布からの標本抽出
- 一般化逆関数の基本性質✓補題 3.2・分布からの標本抽出
- 半直線による判定✓系 3.3・確率変数と期待値
  - 確率変数定義 3.1・確率変数と期待値
  - 生成系による可測性の判定✓命題 3.2・確率変数と期待値
    確率変数定義 3.1・確率変数と期待値
- 分布は確率測度であり、分布関数がそれを決める✓命題 3.6・確率変数と期待値
  - 生成系による可測性の判定✓命題 3.2・確率変数と期待値（上で展開済み）
一般化逆関数（分位点関数）定義 3.1・分布からの標本抽出

これを使っている定理証明で参照している 1 件

生成の決定性と、浮動小数点演算の順序✓命題 6.3・推論

関連するノック 1 問

LLM アーキテクチャ第 45 問