ランダムな文字列と最小のKolmogorovの十分な統計量の間のアルゴリズム相互情報

以下の表記法に関して、関数$ ell(B)$はビット列$ B $の長さを返し、集合$ S $の基数は$ | S |
$で表されます。

ビットストリング$ B $は、均一な分布から0と1を引き出して生成され、長さは$ n = ell(B)$です。

ビットストリング$ B $に対するKolmogorovの複雑さは、$ B $、$ K(B)= ell(B ^
*)$を生成する最短のプログラム$ B ^ * $の長さです。

典型的な$ B
$は正確に定義するのが難しい。直観的には、0と1を無作為に描くことによってほとんどの場合生成されるビットストリングのようなものです。しかし、この概念はプロパティを調べることで明確にすることができます。
$ ell(B)$が増加するにつれて、そのプロパティを持つ$ B $の割合が1に近づくと、プロパティ$ p $が典型的な$ B $
sに適用され、 begin {align *} (B) wedge ell(B) leq n } |} {|
{B: ell(B)} leq n } |} rightarrow 1。 end {align *}

例えば、典型的な$ B $は$ K(B)= ell(B)$という性質を持つ。換言すれば、典型的な$ B
$は圧縮可能ではない。注:これは典型性のための十分な条件ではありません。 $ B
$は非典型的かつ非圧縮性である可能性があります。

There are atypical $B$s that can be compressed, and for these
$K(B) < ell(B)$.

条件付きKolmogorovの複雑さ、$ K(B_2 | B_1)$は、$ B_1 $を入力として$ B_2
$を生成する最短プログラムの長さです。

アルゴリズム相互情報量は$ I(B_1:B_2)= K(B_2) – K(B_2 | B_1 ^ *)= K(B_1) –
K(B_1 | B_2 ^ *)$です。この式は、$ B_1 $と$ B_2 $とは独立した定数内で正確です。

ビット列$ B $の Kolmogorov構造関数は、次のような設定プログラム$ P_B
$を生成します。入力として$ n $が与えられたとき、$ B $は$ P_B $によって生成された集合$ S_B $にあります。 $
ell(P_B)+ log_2(| S_B |) leq K(B)$のような最短の$ P_B $は、$ P ^ * _ B
$で示される最小Kolmogorov構造関数と呼ばれます。 $ log_2(| S_B |)$は$ P ^ * _ B
$で捕捉できない$ B $の “ランダム性”に近い。

典型的な$ B $の場合、$ P ^ * _ B $の長さは最小です。$ n $を知っているので、一定のサイズのプログラム$ C
$で長さ$ n $のすべてのビット列を列挙できます。一方、非定型$ B $ sの場合、$ P ^ * _ B $の長さは$ C
$よりかなり大きくなる可能性があります。

私の質問:一般的な$ B $と$ P ^ * _ {B ‘} $の間のアルゴリズム的な相互情報は、ビットストリング$ B’
$を$ C $よりも大きくしますか?この場合、$ ell(B ‘)$は$ ell(B)$によって制約されませんが、$ P ^
* _ {B’} $は$ n = ell(B)$で提供されます。目標は$ B $を生成することです。しかし、これは$
ell(B)$が必ず$ P ^ * _ {B ‘} $に$ B $を含む集合を生成させるわけではないので、S_ {B’} $の$ B
を意味するものではありません。

Note in the case of a typical $B$ that trivially
$I(P^*_B:B)=ell(C)$ since $ell(P^*_B)=ell(C)$. However, this
does not mean that there is not another $P^*_{B’}$ from an atypical
$B’$ such that $K(B|P^*_{B’}) < K(B)-ell(C)$, and thus
$I(P^*_{B’}:B) > ell(C)$.

I think the answer is always $I(B:P^*_{B’}) = ell(C)$ for a
typical $B$. If $K(P^*_{B’}|B) < K(P^*_{B’})-ell(C)$, then part
of the randomness of $B$ describes $P^*_{B’}$, so $P^*_{B’}$ is not
a minimal structure function for $B’$. I don’t know how to prove
this formally.

To provide context for this question, I am trying to derive a
law of minimal Kolmogorov sufficient statistic nongrowth, based on
Leonid Levin’s conservation independence in “Randomness Conservation Inequalities;
Information and Independence in Mathematical Theories”
. Levin’s
law states $I(z:y) > I(x:y)$ where $x$ is the result of applying
a Turing machine $U$ to $z$, so $x=U(z)$. I would like to similarly
prove $ell(P^*_z) > ell(P^*_x)$, and am using
$I(B:P^*_{B’})=ell(C)$ for typical $B$ as one of the premises in
my proof.

ベストアンサー

EDIT 2: Updated the answer for the updated
definition of typical.


私はあなたの$ P ^ * _ {B ‘}
$の定義を誤解しているかもしれません。その注意書きで、私はあなたの推測が成立しないと信じています。証明は2つのステップで行われます。

Lemma 1. For some $c_0>0$, for all
$n>0$, there are strings $B$ and $B’$ such that $K(P^*_{B’} | B)
le c_0$ and $K(P^*_{B’}) = ell(B) ge n$.

Proof sketch. Let $c_0$ be the length of any universal
TM. Fix any $n>0$.

  1. $ K(P ^ * _ {B ‘}) ge 2n $のような任意の文字列$ B’ $を修正します。 ($ B
    ‘$が存在するという仮定の下で議論する)

  2. $ B $を$ P ^ * _ {B ‘} $を生成する最短のプログラムとすると$ K(P ^ * _ {B’})=
    ell(B)/p>

  3. 与えられた入力$ B $、汎用TMは$ P ^ * _ {B ‘} $を出力するので、

  4. と$ K(P ^ * _ {B’} | B) le c_0 $。 p>

ここにステップ1の正当性があります。$ B
‘$が存在しない場合、最小限のKolmogorov構造関数しか有限ではありません。これは、$ B(P ^ * _ {B ‘}) le
K(P ^ * _ {B’})= O(1) $ B ‘$であり、推測は自明に真である(少なくとも一定である)。また、投稿は
“一方、非典型的な$ B $ sの場合、$ P ^ * _ {B} $の長さは$ C
$よりもかなり大きいかもしれません。”

おそらく、このトピックについてもっと知っている人なら、無限に多くのKolmogorov構造関数が存在することを確認できます。 $ ~~
Box $

これは補題1の証明のスケッチを終わらせる。次に、推測が成り立たないことを示す。

Lemma 2. For any $c > 0$, there are
$epsilon>0$ and a string $B’$ such that, for all sufficiently
large $n$, for a random $n$-bit string $B$, with probability at
least $epsilon$, $I(B : P^*_{B’}) ge c$.

Proof. Fix any $c> 0$. Assume WLOG that $cge c_0$
from Lemma 1, and $c + log(c) + c_1 + c_2 le 2c$ for fixed
constants $c_1, c_2$ defined in Steps 4 and 5 below. (Otherwise
just increase $c$.)

  1. $ K(P ^ * _ {B ‘} | B_0) le c $と$ K(P ^ * _ {B’})=となるような文字列$
    B_0 $と$ B ‘ ell(B_0) ge 4c $です。 (これらは補題1によって存在する)。

  2. $ epsilon = 2 ^ { – ell(B_0)} $とします。任意の$ n ge
    ell(B_0)$を考え、$ B $をランダムな$ n $ビット文字列とする。

  3. $ B_0 $が接頭辞$ B $であるイベントは、少なくとも$ epsilon
    $の確率で発生します。このイベントが発生したとします。証明を完成させるために$ I(B:P ^ * _ {B ‘}) ge c
    $を表示します。

  4. $$ K(P ^ * _ {B ‘} | B) le K(P ^ * _ {B’} | B_0)+ K(B_0 | B)+
    c_1 $$ $ B_0 $から$ B_0 $を計算し、次に$ B_0 $から$ P ^ * _ {B ‘}
    $を計算することができるので、(固定の$ c_1 $に対して) > (B_0)+ c_2(1)の$ K(B ^ 0 | B)
    le log ell $(B ^ 0)$バイトに切り捨てられたTMを使って、いくつかの固定$ c_2 $については、これは$$
    K(P ^ * _ {B ‘} | B) le c + log ell(B_0)+ c_1 + c_2 le
    ell(B_0)/ 2。$$ (ステップ1の$ c $と$ ell(B_0) ge 4c
    $についての上記の仮定を使用してください)。

  5. これを$ 1(B:P ^ * _ {1})とすると、 B ‘})= K(P ^ * _ {B’})-K(P ^ * _ {B ‘} |
    B) ge ell(B_0) – ell(B_0)/ 2 ge 2c。$ $ $ Box $

私はこれが証明を完了したと思うが、ポストの次のステートメントのために、私が投稿を適切に解釈したかどうかは分からない。 “$ P
^ * _ {B ‘} $は$ n = “$ B $を生成することが目標であるので、この場合は
ell(B)$となります。”これは、$ P ^ * _の以前の定義と矛盾しているように、ポストの{B ‘}
$(上記の証明で使用されています)。

返信を残す

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