スターリングの公式の情報理論的解釈

2
Malkoun 2019-09-29 16:11.

情報理論を使ったスターリングの公式の解釈を探しています。

あなたが持っているとしましょう $n$ さまざまなオブジェクトと $n$異なるラベル。がある$n!$2つの異なるオブジェクトに同じラベルが割り当てられないという条件で、オブジェクトにラベルを割り当てるさまざまな方法。したがって、対応するエントロピーは$\log_2(n!)$

このエントロピーは、各オブジェクトのエントロピーの合計以下です。オブジェクトを修正すると、$n$それぞれが等しい確率で発生する可能性のあるラベル。したがって、各オブジェクトにはエントロピーがあります$\log_2(n)$

したがって、 $\log_2(n!) \leq n\log_2(n)$

私の質問は、スターリングの公式で次の項を取得する方法です($-n\log_2(e)$)少なくとも直感的に、そして情報理論を使用して、 $n$ は大きい?

1 answers

2
Jack D'Aurizio 2019-09-29 23:58.

楽しみのために:素数定理を利用するだけで十分です $\pi(n)\sim\frac{n}{\log n}$。レジェンドレの定理$\nu_p(n!)$ 保証します

$$ n! = \prod_{p\leq n} p^{\lfloor\frac{n}{p}\rfloor+\lfloor\frac{n}{p^2}\rfloor+\ldots}\leq \prod_{p\leq n}p^{\frac{n}{p-1}} $$ これはかなり大雑把な限界ですが、すでに十分です:

$$ \log(n!) \leq n\sum_{p\leq n}\frac{\log(p)}{p-1}=n\sum_{m\leq n}\mathbb{1}_p(m)\frac{\log m}{m-1}\stackrel{\text{SBP}}{=}\underbrace{n\pi(n)\frac{\log n}{n-1}}_{O(n)}+n\sum_{m\leq n-1}\pi(m)\left[\frac{\log m}{m-1}-\frac{\log(m+1)}{m}\right].$$ ここに $\mathbb{1}_p$ 素数の特性関数であり、 $\pi$ 素数計数関数であり、 $\text{SBP}$部分和分を表します。最後の合計では、主な用語は次のように動作します$\frac{1}{m}+O\left(\frac{\log m}{m^2}\right)$、したがって $$\log(n!) = O(n)+n\sum_{m\leq n-1}\frac{1}{m} =n\log(n)+O(n).$$ もちろん、これは極端な不正行為です。歴史的に言えば、PNTの弱い形式は、の漸近解析から派生したものです。$n!$ または $\binom{2n}{n}$、ここでは正反対のことを行いました。より基本的なアプローチは、それを考慮することです $$ \frac{4^n}{\sqrt{n+1}}<\binom{2n}{n}=\frac{(2n)!}{n!^2}<4^n $$ ここで、右側の不等式は自明であり、左側の不等式は $\binom{2n}{n}=\sum_{k=0}^{n}\binom{n}{k}^2$とコーシーシュワルツ。モーメントの理論によれば、以前の不等式は次の非整数値に当てはまります。$n$、そうすることによって $L(n)=\log(n!)$ 我々は持っています

$$ L(n)-2 L(n/2) < n\log(2), $$ $$ 2L(n/2)- 4L(n/4) < n\log(2), $$ $$ 4L(n/4)- 8 L(n/8) < n\log(2), $$ $$ \ldots $$

そして

$$ L(n) - 2^k L\left(\frac{n}{2^k}\right) \leq kn\log(2). $$ 選ぶことによって $k\approx \log_2(n)=\frac{\log(n)}{\log(2)}$ 請求 $L(n)\sim n\log n$ 証明されています。

MORE COOL STUFF

ケイト・ブランシェットは3日間一緒に夫と一緒に寝て、25年経ってもまだ夫と結婚しています

ケイト・ブランシェットは3日間一緒に夫と一緒に寝て、25年経ってもまだ夫と結婚しています

ケイト・ブランシェットは、夫に会ったとき、典型的な交際のアドバイスに逆らいました。

マイケルシーンが非営利の俳優である理由

マイケルシーンが非営利の俳優である理由

マイケルシーンは非営利の俳優ですが、それは正確にはどういう意味ですか?

ホールマークスターのコリンエッグレスフィールドがRomaDramaLiveでスリル満点のファンと出会う![エクスクルーシブ]

ホールマークスターのコリンエッグレスフィールドがRomaDramaLiveでスリル満点のファンと出会う![エクスクルーシブ]

特徴的なスターのコリン・エッグレスフィールドは、RomaDrama Liveでのスリル満点のファンとの出会いについて料理しました!加えて、大会での彼のINSPIREプログラム。

「たどりつけば」をオンラインでストリーミングできない理由

「たどりつけば」をオンラインでストリーミングできない理由

ノーザンエクスポージャーが90年代の最も人気のある番組の1つになった理由を確認するには、Blu-rayまたはDVDプレーヤーをほこりで払う必要があります。

バイオニック読書はあなたをより速く読むことができますか?

バイオニック読書はあなたをより速く読むことができますか?

BionicReadingアプリの人気が爆発的に高まっています。しかし、それは本当にあなたを速読術にすることができますか?

ドミニカのボイリング湖:アクセスは簡単ではありませんが、ハイキングする価値があります

ドミニカのボイリング湖:アクセスは簡単ではありませんが、ハイキングする価値があります

ドミニカのボイリング湖は、世界で2番目に大きいボイリング湖です。そこにたどり着くまでのトレッキングは大変で長いですが、努力する価値は十分にあります。

私たちの水をきれいに保つのを助けるためにあなたの髪を寄付してください

私たちの水をきれいに保つのを助けるためにあなたの髪を寄付してください

サロンからのヘアトリミングや個人的な寄付は、油流出を吸収して環境を保護するのに役立つマットとして再利用できます。

ホワイトハウスの最も記憶に残る結婚式を見てください

ホワイトハウスの最も記憶に残る結婚式を見てください

過去200年以上の間にホワイトハウスで結婚したのはほんの数人です。彼らは誰でしたか、そしてそこで結婚式を獲得するために何が必要ですか?

驚くほど素晴らしいDropMixミュージックミキシングカードゲームは30ドルで驚くべき取引です

驚くほど素晴らしいDropMixミュージックミキシングカードゲームは30ドルで驚くべき取引です

DropMixはNFC対応のカードゲームで、基本的にはリミックスアーティストになります。現在、Amazonでは$ 30まで下がっており、これまでで最高の価格に匹敵します。ロックバンドで有名なHarmonixによって開発されたDropMixは、おそらく少し野心的すぎるように思われます。結局のところ、ほとんどの人は素晴らしいリズムを持っていませんが、ゲームは驚くほどうまく実行されます。

メアリーJ.ブライジがついにハリウッドウォークオブフェイムスターを獲得

メアリーJ.ブライジがついにハリウッドウォークオブフェイムスターを獲得

写真:APメアリーJ.ブライジは、間もなくハリウッドウォークオブフェイムのスターを獲得します。これは、メアリーJよりもハリウッドウォークオブフェイムのほうが正直なところ恩恵です。

MeltdownとSpectreの脆弱性についてこれまでに知っていることはすべて、簡単な方法で説明されています

MeltdownとSpectreの脆弱性についてこれまでに知っていることはすべて、簡単な方法で説明されています

画像:グラズ工科大学/ NataschaEiblがデザインしたロゴ。MeltdownとSpectreは、攻撃者がシステムメモリに保存されているあらゆる種類の情報にアクセスできるようにする2つの脆弱性に付けられた名前です。

彼のニューヨークの家から追い出されようとしている97歳の第二次世界大戦の獣医。メリーエフィングクリスマス

彼のニューヨークの家から追い出されようとしている97歳の第二次世界大戦の獣医。メリーエフィングクリスマス

日本人に襲われたときに真珠湾にいた97歳の第二次世界大戦のベテランが、ニューヨークのブルックリンから追い出されています。

Zendaya Wishes Boyfriend Tom Holland Happy Birthday with Cuddly Photo: He 'Makes Me the Happiest'

Zendaya Wishes Boyfriend Tom Holland Happy Birthday with Cuddly Photo: He 'Makes Me the Happiest'

Zendaya shared a sweet photo in honor of boyfriend Tom Holland's 26th birthday Wednesday

小さな女性:脳卒中を患った後に病院から解放されたアトランタのジューシーな赤ちゃん:「まだ癒し」

小さな女性:脳卒中を患った後に病院から解放されたアトランタのジューシーな赤ちゃん:「まだ癒し」

シーレン「Ms.JuicyBaby」ピアソンは、先月脳卒中で入院した後、「もう一度たくさんのことをする方法を学ばなければならない」ため、言語療法を受けていることを明らかにしました。

エマストーンは彼女のクリフサイドマリブビーチハウスを420万ドルでリストアップしています—中を見てください!

エマストーンは彼女のクリフサイドマリブビーチハウスを420万ドルでリストアップしています—中を見てください!

オスカー受賞者の世紀半ばの家には、3つのベッドルーム、2つのバス、オーシャンフロントの景色があります。

ジーニー・メイ・ジェンキンスは、母乳育児の経験の中で、彼女は「本当に、本当に落ち込んでいる」と言います

ジーニー・メイ・ジェンキンスは、母乳育児の経験の中で、彼女は「本当に、本当に落ち込んでいる」と言います

ジーニー・メイ・ジェンキンスは、生後4か月の娘、モナコに母乳育児をしていると語った。

投資ノート:Bioscout AU$300万シード

投資ノート:Bioscout AU$300万シード

Bioscoutは、農家を運転席に置くという使命を負っています。Artesian(GrainInnovate)やUniseedと並んで、最新のシードラウンドでチームを支援できることをうれしく思います。問題真菌症による重大な作物の損失は、農民にとって試練であることが証明されています。

リトルマーケットリサーチ1| 2022年のクイックグリンプス遠隔医療市場

リトルマーケットリサーチ1| 2022年のクイックグリンプス遠隔医療市場

遠隔医療は、パンデミック後の時代では新しいものではなく、時代遅れの分野でもありません。しかし、業界を詳しく見ると、需要と供給の強力な持続可能性と、米国で絶え間ない革命となる強力な潜在的成長曲線を示しています。

スタートアップ資金調達環境:タイのスタートアップエコシステムの次は何ですか?

スタートアップ資金調達環境:タイのスタートアップエコシステムの次は何ですか?

2021年は、世界的なベンチャーキャピタル(VC)の資金調達にとって記録的な年でした。DealStreetAsiaによると、東南アジアも例外ではなく、この地域では年間で記録的な25の新しいユニコーンが採掘されました。

ムーアの法則を超えて

ムーアの法則を超えて

計算に対する私たちの欲求とムーアの法則が提供できるものとの間には、指数関数的に増大するギャップがあります。私たちの文明は計算に基づいています—建築と想像力の現在の限界を超える技術を見つけなければなりません。

Language