有効寸法

数学において、有効次元はハウスドルフ次元やその他のフラクタル次元を修正したもので、計算可能性理論の枠組みに位置づけられます。有効次元には様々なバリエーション（様々な概念）があり、最も一般的なのは有効ハウスドルフ次元です。数学における次元とは、物体の大きさを記述する特定の方法であり、測度やその他の異なる大きさの概念とは対照的です。ハウスドルフ次元は、点、直線、平面などに割り当てられるよく知られた整数次元を一般化し、これらの整数次元の物体間の中間の大きさを持つ物体を区別することを可能にします。例えば、平面のフラクタル部分集合は、直線や曲線よりも「大きく」、塗りつぶされた円や長方形よりも「小さい」ため、1と2の中間の次元を持つ場合があります。有効次元は、有効次元が小さい物体は小さいだけでなく、計算可能な意味で配置可能（または部分的に配置可能）であることを要求することで、ハウスドルフ次元を修正します。このように、ハウスドルフ次元が大きい物体は実効次元も大きく、実効次元が小さい物体はハウスドルフ次元も小さくなります。しかし、ハウスドルフ次元は小さくても実効次元が大きい物体も存在します。例えば、直線上のアルゴリズム的にランダムな点は、ハウスドルフ次元が0（点であるため）ですが、実効次元は1です（大まかに言えば、ハウスドルフ次元が1である小さな区間よりも効果的に局所化できないため）。

厳密な定義

本稿では、カントール空間 2 ^{ωの部分集合の有効次元を定義します。}ユークリッド空間 R ⁿの部分集合にも、これと密接に関連する定義が存在します。ここでは、自然数の集合X 、 Xの特性関数によって与えられる無限列、そして二進展開 0. Xを持つ実数について、自由に考察を進めていきます。 ${\displaystyle \chi _{X}}$

マーチンゲールとその他のゲール

カントール空間2ω上のマルチンゲール^は、カントール空間から非負実数への関数d : 2ω → R ^{≥ 0で}あり、公平性条件を満たす。

${\displaystyle d(\sigma )={\frac {1}{2}}(d(\sigma 0)+d(\sigma 1))}$

マーチンゲールは賭け戦略の一つと考えられており、この関数は0と1のシーケンスσを見た後の、より良い方の資本を与えます。公平性条件は、シーケンスσ後の資本は、σ0とσ1を見た後の資本の平均であるということです。言い換えれば、マーチンゲールはブックメーカーにとって、2つの「等確率」の選択肢のどちらにも2:1のオッズを提供する賭けスキームを与えるため、「公平」という名前が付けられています。 ${\displaystyle d(\sigma )}$

（これは確率論におけるマルチンゲールの概念とは微妙に異なることに注意してください。^[1]マルチンゲールの定義には同様の公平性条件があり、観測の事前履歴が与えられた場合、ある観測後の期待値は観測前の値と同じであるとも述べています。違いは、確率論では観測の事前履歴は単に資本の履歴を指すのに対し、ここでは履歴は文字列内の0と1の正確なシーケンスを指すことです。）

カントール空間上のスーパーマルチンゲールは、修正された公平性条件を満たす上記のような 関数dです。

${\displaystyle d(\sigma )\geq {\frac {1}{2}}(d(\sigma 0)+d(\sigma 1))}$

スーパーマーチンゲールとは、賭け後の期待資本が賭け前の資本と変わらない賭け戦略です。これは、両者が常に等しいマーチンゲールとは対照的です。これにより柔軟性が高まり、非効率的なケースと非常によく似ています。スーパーマーチンゲールdが与えられるたびに、少なくともdと同額の賞金を獲得する修正関数d'が存在し、これは実際にはマーチンゲールです。しかし、賭け戦略を決定するアルゴリズムを実際に提供するという話になると、この追加の柔軟性を考慮することは有用です。なぜなら、アルゴリズムによっては、マーチンゲールよりもスーパーマーチンゲールを生成する方が自然だからです。

s-ゲイルは、上記のように dの関数であり、

${\displaystyle d(\sigma )={\frac {e(\sigma )}{2^{(1-s)|\sigma |}}}}$

いくつかのマーチンゲールの場合。

s-超強風は、上記のように dの関数であり、

${\displaystyle d(\sigma )={\frac {e(\sigma )}{2^{(1-s)|\sigma |}}}}$

いくつかのスーパーマーチンゲールの場合。

s- （スーパー）ゲールとは、各ステップで一定額の資本がインフレによって失われる賭け戦略です。s-ゲールとs-スーパーゲールはスーパーマルチンゲールの例であり、1-ゲールと1-スーパーゲールはまさにマルチンゲールとスーパーマルチンゲールであることに注意してください。

これらの物体は総称して「強風」と呼ばれます。

ゲイルd は 、自然数のサブセットXで、 Xの最初のn桁からなるn桁の文字列を表す場合、成功します。 ${\displaystyle \limsup _{n}d(X|n)=\infty }$ ${\displaystyle X|n}$

強風d は、 X上で次の条件を満たす場合に強く成功します。 ${\displaystyle \liminf _{n}d(X|n)=\infty }$

様々な強風に関するこれらの概念はどれも実質的な内容を持たないが、与えられた集合において成功する強風が存在するため、必然的に強風のクラスを限定せざるを得ない。結局のところ、コイン投げの順序が事前に分かっていれば、各投げの既知の結果に賭けるだけで簡単に金儲けができる。これを実現するための標準的な方法は、強風が計算可能か、それに近いことを条件とすることである。

数が一様に左 ce 実数である場合（つまり、有理数の増加計算可能シーケンスの極限として一様に記述できる場合）、 ゲイルdは構成的、ce、または下位半計算可能と呼ばれます。${\displaystyle d(\sigma )}$

自然数集合Xの有効ハウスドルフ次元はである。^[2]${\displaystyle \inf\{s:\mathrm {some\ c.e.} \ s\mathrm {-gale\ succeeds\ on\ } X\}}$

Xの有効充填寸法はである。^[3]${\displaystyle \inf\{s:\mathrm {some\ c.e.} \ s\mathrm {-gale\ succeeds\ strongly\ on\ } X\}}$

コルモゴロフ複雑性の定義

コルモゴロフ複雑度は、有限の文字列（文字または2進数字）のアルゴリズム的圧縮可能性の下限値と考えることができます。コルモゴロフ複雑度は、各文字列wに自然数K(w)を割り当てます。これは直感的に、入力を必要とせず実行時にwを出力するコンピュータプログラム（特定のプログラミング言語で記述されたもの）の最小の長さを表します。

自然数集合Xの有効ハウスドルフ次元は^{[4] [5] [6] [7]}である。${\displaystyle \liminf _{n}{\frac {K(X|n)}{n}}}$

集合Xの有効パッキング寸法は^{[3] [4] [5]}である。${\displaystyle \limsup _{n}{\frac {K(X|n)}{n}}}$

このことから、集合の有効ハウスドルフ次元と有効パッキング次元はどちらも0から1の間であり、有効パッキング次元は常に有効ハウスドルフ次元と少なくとも同じ大きさであることがわかります。すべてのランダムシーケンスの有効ハウスドルフ次元とパッキング次元は1ですが、有効ハウスドルフ次元とパッキング次元が1である非ランダムシーケンスも存在します。

古典的な次元との比較

Z^が2ωの部分集合である場合、そのハウスドルフ次元はである。^[2]${\displaystyle \inf\{s:\mathrm {some} \ s\mathrm {-gale\ succeeds\ on\ all\ elements\ of\ } Z\}}$

Zのパッキング次元はである。^[3]${\displaystyle \inf\{s:\mathrm {some} \ s\mathrm {-gale\ succeeds\ strongly\ on\ all\ elements\ of\ } Z\}}$

したがって、ce gales に着目する場合、 セットの有効ハウスドルフ次元とパッキング次元は、それぞれ単に古典的なハウスドルフ次元とパッキング次元になります。${\displaystyle X}$ ${\displaystyle \{X\}}$

以下を定義します。

${\displaystyle H_{\beta }:=\{X\in 2^{\omega }:X\ \mathrm {has\ effective\ Hausdorff\ dimension\ } \beta \}}$

${\displaystyle H_{\leq \beta }:=\{X\in 2^{\omega }:X\ \mathrm {has\ effective\ Hausdorff\ dimension\ } \leq \beta \}}$

${\displaystyle H_{<\beta }:=\{X\in 2^{\omega }:X\ \mathrm {has\ effective\ Hausdorff\ dimension\ } <\beta \}}$

${\displaystyle P_{\beta }:=\{X\in 2^{\omega }:X\ \mathrm {has\ effective\ packing\ dimension\ } \beta \}}$

${\displaystyle P_{\leq \beta }:=\{X\in 2^{\omega }:X\ \mathrm {has\ effective\ packing\ dimension\ } \leq \beta \}}$

${\displaystyle P_{<\beta }:=\{X\in 2^{\omega }:X\ \mathrm {has\ effective\ packing\ dimension\ } <\beta \}}$

上記の結果から、これらはすべてハウスドルフ次元を持つことになる。^[8]${\displaystyle \beta }$

${\displaystyle H_{\beta },H_{\leq \beta }}$ いずれも梱包寸法は 1 です。 ${\displaystyle H_{<\beta }}$

${\displaystyle P_{\beta },P_{\leq \beta }}$ すべて梱包寸法 です。 ${\displaystyle P_{<\beta }}$ ${\displaystyle \beta }$

参考文献

1. John M. Hitchcock、Jack H. Lutz (2006). 「なぜ計算複雑性にはより厳格なマルチンゲールが必要なのか」『計算システム理論』
2. Jack H. Lutz (2003). 「複雑性クラスにおける次元」SIAM Journal on Computing . 32 (5): 1236– 1259. arXiv : cs/0203016 . doi :10.1137/s0097539701417723.
3. Krishna B. Athreya; John M. Hitchcock; Jack H. Lutz; Elvira Mayordomo (2007). 「アルゴリズム情報と計算複雑性における有効な強次元」. SIAM Journal on Computing . 37 (3): 671– 705. arXiv : cs/0211025 . doi :10.1137/s0097539703446912. S2CID  27038.
4. Jin-yi Cai; Juris Hartmanis (1994). 「実数直線のコルモゴロフ複雑性のハウスドルフ次元と位相次元について」. Journal of Computer and System Sciences . 49 (3): 605– 619. doi : 10.1016/S0022-0000(05)80073-X .
5. ルートヴィヒ・シュタイガー (1993)。 「コルモゴロフの複雑さとハウスドルフの次元」。情報と計算。103 (2): 159–194 .土井: 10.1006/inco.1993.1017。
6. Elvira Mayordomo (2002). 「構成的ハウスドルフ次元のコルモゴロフ複雑性による特徴づけ」. Information Processing Letters . 84 : 1–3 . doi :10.1016/S0020-0190(02)00343-5.
7. Ludwig Staiger (2005). 「構成次元はコルモゴロフ複雑度に等しい」. Information Processing Letters . 93 (3): 149– 153. doi :10.1016/j.ipl.2004.09.023. hdl : 2292/3717 .
8. Boris Ryabko (1994). 「組み合わせ情報源の符号化とハウスドルフ次元」.ソビエト数学 - Doklady .