数学におけるつながり：ランダムの二種類

免責事項：この記事の執筆にAIは使用されていません。誤り、不自然な文章、奇妙な脱線はすべて100％オーガニックで、自由に飼育され、人間が作ったものです。 以前の記事で触れたパズルを拾い上げる 前回、私はパズルを提示して、それを放置してしまいました。今回もそれを提示します。なぜなら、この記事全体が、私がそれを手放すことを拒否しているようなものだからです。 2つのファイルがあると想像してください。それぞれに100万桁の数字が入っています。最初のファイルは純粋なノイズです。10面ダイスを100万回振って、その結果を書き留めたと想像してください。2番目のファイルは、円周率πの最初の100万桁です。 統計学者のようにそれらを見てみましょう：0から9までの各数字が何回出現するかを数えます。両方のファイルで、各数字は約10分の1の確率で出現します。そのため、2つのヒストグラムをプロットしても、それらを区別することはできません。どちらも平坦で、特徴がありません。そして、あなたが好きな「これはランダムか？」というテストをどれだけ実行しても、両方のファイルは合格するでしょう。あらゆる統計的尺度において、この2つのファイルは同じです。どちらも純粋で、圧縮不可能なランダムネスのように見えます。 しかし。 これらのファイルのうち1つは、3行であなたに送ることができます。私はあなたに小さなプログラムを書きます。「πを計算して、100万桁表示する」というプログラムです。あなたはファイルを正確に再生できます。もう1つのファイルは、まったく短縮できません。あなたに送るためには、数字ごとに、その全体を送らなければなりません。なぜなら、それ自身よりも短い説明がないからです。 したがって、この記事全体の質問はこれです：2つのファイルが統計的に同一であるなら、なぜ私は一方を圧縮できて、もう一方を圧縮できないのでしょうか？ この問題には簡単な答えがなく、それがまさに興味深い点だと私は思います。それについて何か進展を得るためには、「圧縮可能」という言葉が実際に何を意味するのかについて注意深くならなければなりません。そして、注意深くなると、それは2つの非常に異なる考えに分かれます。この記事のほとんどは、それら2つを分離すること、そして2番目のものに待っている驚きについてです。それは、存在するときはいつでも確認できるが、存在しないときは決して排除できない種類の圧縮可能性です。 圧縮の2種類 最初にはっきりさせておきたいことがあります。この記事のすべては、ロスレス圧縮に関するものです。これは、何も捨てられず、何も近似されないことを意味します。私はあなたに短い説明を送り、あなたはそれから元のものをビット単位で正確に再構築します。その厳格なルールでも、物事が圧縮可能であるには本当に2つの異なる理由があると思います。そして、この記事は主にそれらを区別することを学ぶことについてです。 最初の理由は統計的です。一部の記号は他の記号よりも頻繁に出現するため、一般的なものには短いコードを、まれなものには長いコードを与え、平均してスペースを節約します。これはzipファイルやハフマンコーディングが行うことであり、ほとんどの人がその言葉を聞いたときに思い浮かべる圧縮の種類だと思います。 2番目の理由はプロセスに関するものです。その物事は、たとえその記号が完全に均等に分散しているように見えても、単純なルール、つまり短いプログラムから来る可能性があります。その場合、利用できる統計的冗長性はまったくありません。それでも、その物事は圧縮されます。なぜなら、短さは記号の頻度ではなく、それを生成するプロセスに宿っているからです。 したがって、この記事の本当の質問は次のとおりです。統計的冗長性だけが圧縮可能性の種類なのでしょうか？そして、πはそうではないと言おうとしています。 統計的な種類：エントロピー 予算からエントロピーを構築する πについて奇妙な点を述べる前に、私たちは「統計的圧縮」が何を測定するのかを正確に定義する必要があります。そして、その測定には名前があります：エントロピーです。 非公式には、エントロピーとは、記号のソースにおける平均的な驚きの量です。ソースが常に同じ記号を発する場合、驚きはまったくありません。あなたはすでに何が来るかを知っているので、新しい各記号は何も教えてくれません。そして、エントロピーはゼロです。ソースが10種類の異なる数字を等しい確率で発行する場合、新しい各記号は可能な限り驚くべきものであり、エントロピーは最大です。ほとんどのソースは、その中間のどこかに位置します。一部の記号は一般的（驚きが少なく、情報が少ない）であり、一部はまれ（驚きが多く、情報が多い）です。そして、エントロピーは、各記号がどれくらいの頻度で出現するかで重み付けされた、それらすべてにわたる平均です。 圧縮との関連は直接的です。驚きとは、ビットを支払う必要があるまさにそのものです。予測可能なものはすべて省略できます。なぜなら、受信者はそれを補うことができるからです。そして、驚くべきものはすべて実際に送信する必要があります。したがって、記号あたりのビットで測定されるソースのエントロピーは、あなたが常に達成できる最短の平均メッセージのサイズです。それは、ロスレスコードが決して下回ることのできない下限です。 それが非公式な絵です。しかし、私は単に式を述べて次に進むのではなく、それを実際に導き出す方法があるので、そうしたくありません。そして、私はクリス・オラーの素晴らしい「Visual Information Theory」からその精神を借りています。以下の図は、彼の議論の私自身のバージョンです。 セットアップは次のとおりです。 私はできるだけ少ないビットを使用して、記号のストリームをあなたに送信したいと考えています。各記号にコードワード、つまり短いビット文字列を与えます。一般的な記号には短いコードワードを与えるべきです。まれな記号には長いコードワードを与えることができます。なぜなら、私はそれらをめったに送信しないからです。それがすべての直感であり、それは明らかに正しいです。 本当の質問は次のとおりです。確率pで出現する記号のコードワードは、正確にどれだけ短いのでしょうか？ ここに、それを本当の質問に変えるひっかけがあります。コードワードは競合します。ストリームを曖昧さなくデコードするには、どのコードワードも他のコードワードのプレフィックスであってはなりません。0がコードワードの場合、他の何も0で始まってはなりません。したがって、短いコードワードを与えることは高価です。それは、まだ利用可能なコードワードの空間の大きな部分を消費します。 正確には、長さLLLのコードワードは、その空間の1/2^Lのスライスを消費します。1ビットのコードワードはすべてを半分消費し、2ビットのコードワードは4分の1を消費します。短いコードワードは希少なリソースであり、それを使用することは他のコードワードを成長させることを強制します。 それを固定予算として考えてください。各記号はコードワードを購入する必要があり、短いコードワードはより高価です。では、どのようにして記号全体に固定予算を費やすのでしょうか？ 自然な動き、そしてそれが最適であることが判明したことは、各記号にそれを使用する頻度に比例して費やすことです。確率pの記号にpサイズの予算のスライスを与えます。サイズpのスライスは、コストpのコードワードを購入します。つまり、1/2^L = pであり、これはL = log2(1/p)を意味します。 そして、そこにあります。主張されたのではなく、導き出されました。確率pの記号に対するコードワードの理想的な長さは、log2(1/p)ビットです。したがって、一般的な記号（pが1に近い）はゼロに近い長さを取得し、まれな記号（pが非常に小さい）は長い長さを取得します。これはまさに私たちが始めた直感ですが、今では数値が付いています。 そして、私が最も好きな部分は次のとおりです。平均メッセージ長を面積として見ることができます。各記号の確率を一方の軸に、コードワード長 log2(1/p) をもう一方の軸に配置します。これにより、各記号は面積 p・log2(1/p) の長方形になり、合計面積は記号あたりの平均ビット数になります。 H = Σ pi log2(1/pi) = - Σ pi log2(pi) それがシャノンエントロピーであり、それは最小の可能な面積です。つまり、この分布に対して任意のコードが達成できる最短の平均メッセージです。一般的な記号に長いコードワードを与えると、多くの面積が追加されます。そして、予算ルールはまさにその無駄を排除するものです。 （log2(1/p)を別の方法で解釈することもできます。それは、確率pの割合を占めるものを分離するために必要な「はい/いいえ」の質問、つまり半減の数です。まれなものには多くの半減が必要であり、一般的なものには少なくて済みます。同じ数、2つのレンズ。） きれいなケースでそれを感じるために、確率が 1/2, 1/4, 1/8, 1/8 の4つの記号を考えてみましょう。この式は、理想的な長さ 1, 2, 3, 3 を割り当てます。そして、実際にそれらのコードワードを構築できます：0, 10, 110, 111。プレフィックスの衝突はありません。平均長は (1/2)(1) + (1/4)(2) + (1/8)(3) + (1/8)(3) = 1.75 ビットです。