転写物の最悪の長さと転写物のエントロピーとの関係

アリスとボブにある分布$ mu $からサンプリングされた入力$ X $と$ Y $が与えられ、その目的は何らかの問題$ P
$を解決することである本当にこの質問のために重要です)。

$ P $を解くための最良の(すなわち最小のビット量の)2パーティプロトコルである$ mathcal {P} $を$
mathcal {を実行するときにアリスとボブの間のメッセージのトランスクリプトを表すようにします。 P} $は$ mu
$からサンプリングされた入力です。すべての入力とランダムビットに対して、$ Pi
$のワーストケースの長さを表すために$ | Pi | $を使用します。

論文内データストリームへの情報統計手法と
通信の複雑さ
を考慮すると、以下の事実が命題4.3の証明に使用されます。

$$ | Pi | ge H [ Pi]、 $$ $ H $はバイナリエントロピーを表します。

$ Pi $の最悪ケースの長さは$ Pi
$の予想不確実性の量より小さくすべきではないので、これは直感的に真実であることがわかりますが、正式にどのように証明できますか?

また、 $$ E [| Pi |] ge H [ Pi]? $$

ベストアンサー

Suppose $|Pi|<log 2^{H(Pi)}=H(Pi)$, contradiction. Note
that $|Pi|$ is constant and not a random variable, so it doesn’t
make much sense to talk about its expectation.

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です