![**ランダム整数のエントロピー**
情報理論において、*エントロピー* \(H\) は、確率変数が取る結果に対する平均的な「驚き」や不確実性の量を定量化します。
離散型で整数値を取り得る確率変数についても、エントロピーは他の任意の離散分布と同じ式で定義されます。
---
### 1. 一般的な公式
ランダム整数 \(X\) が異なる値
\(\{x_1, x_2, \dots , x_n\}\) を取り、確率
\(P(X=x_i)=p_i\)（\(p_i \ge 0\)、かつ \(\sum_{i=1}^{n} p_i = 1\）とすると、
\[
H(X) \;=\; -\,\sum_{i=1}^{n} p_i \log_2 p_i .
\]
- **単位**：ビット（対数の底が \(2\) の場合）。
自然対数 (\(\ln\)) や常用対数 (base‑10 log) を使うと、結果はナットやバンになります。
---
### 2. よくあるケース
| 分布 | エントロピー式 |
|------|----------------|
| **一様分布** \(\{1,\dots,N\}\) | \(H = \log_2 N\) ビット |
| **幾何分布**（成功確率 \(p\)） | \(H = -\,\dfrac{(1-p)\log_2(1-p)+p\log_2 p}{p}\) |
| **ポアソン分布**（平均 \(\lambda\)） | \(H \approx \tfrac12\log_2(2\pi e \lambda)\) （\(\lambda\) が大きいとき） |
---
### 3. 本質的な直感
- 大きい範囲の **一様整数** は不確実性が高く、可能な値が増えるごとに等しい確率を持つ結果数が2倍になるため、エントロピーは1ビットずつ増加します。
- 分布が極端に偏っている（例えばある結果だけが支配的）場合、変数はほぼ決定論的となり、エントロピーは 0 に近づきます。
---
### 4. 実践例
公平な6面ダイスを振ると、\(X \in\{1,\dots,6\}\) で \(p_i=1/6\)。
\[
H(X)= -\,6 \times \frac16 \log_2 \frac16 = \log_2 6 \approx 2.585~\text{ビット}.
\]
したがって、1回のダイスロールは約 **2.59 ビット** の情報を伝えます。
---
### 5. 重要なポイント
ランダム整数のエントロピーは、その確率分布に対するシャノンエントロピーであり、標準的な離散型エントロピー式で計算されます。具体的な値は、すべてその分布の確率に依存します。](/_next/image?url=%2Fscreenshots%2F2026-02-10%2F1770680484560.webp&w=3840&q=75)
2026/02/05 18:47
**ランダム整数のエントロピー** 情報理論において、*エントロピー* \(H\) は、確率変数が取る結果に対する平均的な「驚き」や不確実性の量を定量化します。 離散型で整数値を取り得る確率変数についても、エントロピーは他の任意の離散分布と同じ式で定義されます。 --- ### 1. 一般的な公式 ランダム整数 \(X\) が異なる値 \(\{x_1, x_2, \dots , x_n\}\) を取り、確率 \(P(X=x_i)=p_i\)（\(p_i \ge 0\)、かつ \(\sum_{i=1}^{n} p_i = 1\）とすると、 \[ H(X) \;=\; -\,\sum_{i=1}^{n} p_i \log_2 p_i . \] - **単位**：ビット（対数の底が \(2\) の場合）。 自然対数 (\(\ln\)) や常用対数 (base‑10 log) を使うと、結果はナットやバンになります。 --- ### 2. よくあるケース | 分布 | エントロピー式 | |------|----------------| | **一様分布** \(\{1,\dots,N\}\) | \(H = \log_2 N\) ビット | | **幾何分布**（成功確率 \(p\)） | \(H = -\,\dfrac{(1-p)\log_2(1-p)+p\log_2 p}{p}\) | | **ポアソン分布**（平均 \(\lambda\)） | \(H \approx \tfrac12\log_2(2\pi e \lambda)\) （\(\lambda\) が大きいとき） | --- ### 3. 本質的な直感 - 大きい範囲の **一様整数** は不確実性が高く、可能な値が増えるごとに等しい確率を持つ結果数が2倍になるため、エントロピーは1ビットずつ増加します。 - 分布が極端に偏っている（例えばある結果だけが支配的）場合、変数はほぼ決定論的となり、エントロピーは 0 に近づきます。 --- ### 4. 実践例 公平な6面ダイスを振ると、\(X \in\{1,\dots,6\}\) で \(p_i=1/6\)。 \[ H(X)= -\,6 \times \frac16 \log_2 \frac16 = \log_2 6 \approx 2.585~\text{ビット}. \] したがって、1回のダイスロールは約 **2.59 ビット** の情報を伝えます。 --- ### 5. 重要なポイント ランダム整数のエントロピーは、その確率分布に対するシャノンエントロピーであり、標準的な離散型エントロピー式で計算されます。具体的な値は、すべてその分布の確率に依存します。
RSS: https://news.ycombinator.com/rss
要約▶
日本語訳:
概要（改訂版）:
この記事では、区間 ([N,2N]) から一様に選ばれた整数 (n) の情報量を調べます。(n) を素因数分解すると
[
n=\prod p_i^{a_i}
]
となり、各素数 (p_i) に対する確率分布は
[
P(p_i)=\frac{a_i\log p_i}{\log n}
]
で与えられ、この分布のシャノンエントロピーを求めることが問題となります。
解析を容易にするため、著者らはまず平方自由整数に限定します。この場合、各素因数は (N) 個の文字からなるランダム置換のサイクルに対応し、これらの長さはポアソン・ディリクレ ((0,1)) 過程に従います。固定されたサイクル長 (i) について、そのようなサイクル数 (X_i) は平均 (1/i) のポアソン分布に近似されます。
各 (i)-サイクルはエントロピーに
[
-\frac{i}{N}\log!\left(\frac{i}{N}\right)
]
を寄与します。すべてのサイクル長について合計すると、期待寄与は
[
\sum_{i=1}^N \frac{i}{N}\bigl(\log N-\log i\bigr).
]
第一項は (\sum_i iX_i=N) であるため (\log N) に等しく、第二項は
[
\frac{1}{N}\sum_{i=1}^N \log i \approx \log N-1
]
と Stirling の近似を用いて評価できます。したがって期待エントロピーは
[
E[H];\approx;\log N-(\log N-1)=1.
]
数値実験では、有限の (N) に対して平均エントロピーがわずかに 1 未満であることが確認され、これは有限サイズ効果を反映しています。
論文は最後に、エントロピー自体が分布的に収束するか（平均だけでなく）、その指数関数であるパープレキシティが明確な期待値を持つかどうかを問い、素因数分解統計と情報理論的概念（エントロピー・パープレキシティ）との関連を示し、エルドウス–カク定理に非公式の類似性を引き出しています。
本文
素因数分布のエントロピー
(n) を ([N,2N]) から一様に選ばれた整数とする。
その素因数分解を
[ n=\prod_{i}p_i^{,a_i} ]
と書く。
各素数 (p_i) が「(n) の大きさ」に与える寄与は
[ w_i=\frac{a_i \log p_i}{\log n}, \qquad \text{すなわち}\qquad \sum_i w_i=1. ]
したがって ((w_1,w_2,\dots)) は (n) の素因数上の確率分布になる。
疑問は「この分布のエントロピーはいくらか？」である。
簡易モデル：平方自由整数
平方自由整数に限定すると、各素数は最大でも一度しか現れない。
そのとき分布は
[ w_i=\frac{\log p_i}{\sum_j \log p_j}, ]
となり、典型的な素因数の大きさは (N) 個の文字列上のランダム置換におけるサイクル長と同じ挙動を示す。
実際、大きな平方自由整数の素因数集合は、等確率置換のサイクル長集合（Poisson–Dirichlet ((0,1))）と同一分布になる。
したがってエントロピーを調べるために次の組合せ的設定で研究できる：
置換モデル – (N) 個の文字列上のランダム置換をサイクルに分解する。
各サイクルには確率 (\frac{\text{サイクル長}}{N}) を割り当てる。
期待エントロピーの計算
(X_i) を置換中の (i)-サイクル数とする。
大きな (N) に対して、変数 (X_i) は平均 (\frac1i) の独立ポアソン乱数として近似できる。
(i)-サイクルがもたらすエントロピーは
[ -\frac{i}{N}\log!\left(\frac{i}{N}\right) ]
で、そうした (X_i) 個のサイクルがあるので、全体の貢献は
[ -\frac{i}{N}X_i,\log!\left(\frac{i}{N}\right) = \frac{i}{N}X_i\bigl(\log N-\log i\bigr). ]
すべてのサイクル長について和を取ると
[ H=\sum_{i=1}^{N}\frac{i}{N}X_i,\log N -\sum_{i=1}^{N}\frac{i}{N}X_i,\log i . ]
第一項。
(\sum_{i} iX_i=N) であるから、最初の和は単に (\log N) になる。
第二項。
(E[X_i]=1/i) を使うと
[ E!\left[\frac{i}{N}X_i,\log i\right] =\frac{1}{N},\log i, \qquad E!\Bigl[\sum_{i=1}^{N}\frac{i}{N}X_i,\log i\Bigr] =\frac{1}{N}\sum_{i=1}^{N}\log i. ]
スターリング公式より
[ \sum_{i=1}^{N}\log i = \log(N!) = N\log N - N + O(\log N). ]
したがって
[ E!\Bigl[\sum_{i=1}^{N}\frac{i}{N}X_i,\log i\Bigr] = \log N - 1 + o(1). ]
まとめ。
[ E[H]=\log N-\bigl(\log N-1\bigr)+o(1)=1+o(1). ]
ゆえに 期待エントロピーは (N\to\infty) のとき 1 に収束する。
補足とさらなる疑問
-
この計算はポアソン変数の第一二次モーメントだけを使っているため、
大きな (N) では高階修正は無視できる。したがって収束は堅牢である。 -
実際の整数（平方自由でない場合）では指数 (a_i>1) が追加項として現れるが、
これらは極限においてエントロピーへの影響を消失させる。 -
エントロピーから求める パープレキシティ (\exp(H)) は (e) に収束する。
その分布は、加算的算術関数の古典的なエルデス–カック現象と同様に鋭く集中する。
結論
素因数サイズを正規化して作られた確率分布（あるいはランダム置換のサイクル長）
そのエントロピーは 1 ビット に収束し、従ってパープレキシティは (e) になる。
これは平均的にランダム整数が「有効な」素因数をほんの少しだけ持つという直感と一致する。