Efektivní rozměr - Effective dimension

v matematika, efektivní dimenze je modifikace Hausdorffova dimenze a další fraktální rozměry který jej umístí do a teorie vypočítatelnosti nastavení. Existuje několik variací (různé pojmy efektivní dimenze), z nichž nejběžnější je efektivní dimenze Hausdorff. Dimenze, v matematice, je zvláštní způsob, jak popsat velikost objektu (v kontrastu s mírou a jinými, odlišnými pojmy velikosti). Hausdorffova dimenze zobecňuje známé celočíselné kóty přiřazené bodům, přímkám, rovinám atd. Tím, že umožňuje rozlišovat mezi objekty střední velikosti mezi těmito celočíselnými objekty. Například, fraktální podmnožiny roviny mohou mít střední rozměr mezi 1 a 2, protože jsou „větší“ než čáry nebo křivky, a přesto „menší“ než vyplněné kruhy nebo obdélníky. Efektivní dimenze upravuje Hausdorffovu dimenzi tím, že vyžaduje, aby objekty s malou efektivní dimenzí byly nejen malé, ale také lokalizovatelné (nebo částečně lokalizovatelné) ve vypočítatelném smyslu. Jako takové mají objekty s velkou Hausdorffovou dimenzí také velkou efektivní dimenzi a objekty s malou efektivní dimenzí mají malou Hausdorffovu dimenzi, ale objekt může mít malou Hausdorffovu, ale velkou efektivní dimenzi. Příkladem je algoritmicky náhodné bod na přímce, která má Hausdorffovu dimenzi 0 (protože je to bod), ale efektivní dimenzi 1 (protože, zhruba řečeno, nemůže být efektivně lokalizována o nic lépe než malý interval, který má Hausdorffovu dimenzi 1).

Přísné definice

Tento článek bude definovat efektivní dimenzi pro podmnožiny Cantorův prostor 2^ω; úzce související definice existují pro podmnožiny souboru Euklidovský prostor Rⁿ. Mezi uvažováním o sadě se budeme volně pohybovat X přirozených čísel, nekonečná posloupnost ${displaystyle chi _ {X}}$ dané charakteristickou funkcí Xa skutečné číslo s binární expanzí 0.X.

Martingales a jiné vichřice

A martingale na Cantorově prostoru 2^ω je funkce d: 2^ω → R^≥ 0 z Cantorova prostoru do nezáporných realit, které splňují podmínku spravedlnosti:

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

Martingale je považován za strategii sázení a funkci ${displaystyle d (sigma)}$ dává kapitál lepšího poté, co viděl sekvenci σ 0 s a 1 s. Podmínka spravedlnosti pak říká, že kapitál po sekvenci σ je průměrem kapitálu po vidění σ0 a σ1; jinými slovy martingale dává sázkové schéma pro bookmakera s kurzem 2: 1 nabízeným na jednu ze dvou „stejně pravděpodobných“ možností, odtud název spravedlivý.

(Všimněte si, že se to nepatrně liší od pojmu teorie pravděpodobnosti o martingale.^[1] Tato definice martingale má podobnou podmínku spravedlnosti, která rovněž uvádí, že očekávaná hodnota po určitém pozorování je vzhledem k předchozí historii pozorování stejná jako hodnota před pozorováním. Rozdíl je v tom, že v teorii pravděpodobnosti předchozí historie pozorování odkazuje pouze na historii kapitálu, zatímco zde historie odkazuje na přesnou sekvenci 0s a 1s v řetězci.)

A supermartingale na Cantorově prostoru je funkce d jak je uvedeno výše, které splňuje upravenou podmínku spravedlnosti:

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

Supermartingale je strategie sázení, kde očekávaný kapitál po sázce není větší než kapitál před sázkou, na rozdíl od martingale, kde jsou oba dva stejné. To umožňuje větší flexibilitu a je velmi podobné v neefektivním případě, protože kdykoli supermartingale d je uvedena upravená funkce d ' který vyhraje alespoň tolik peněz jako d a který je vlastně martingale. Je však užitečné umožnit dodatečnou flexibilitu, jakmile začnete hovořit o tom, že skutečně dáváte algoritmy k určení strategie sázení, protože některé algoritmy se přirozeněji hodí k produkci supermartingales než martingales.

An s-vichřice je funkce d jak je uvedeno výše ve formuláři

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

pro E nějaký martingale.

An s-supergale je funkce d jak je uvedeno výše ve formuláři

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

pro E nějaký supermartingale.

An s- (super) vichřice je strategie sázení, při které se v každém kroku ztrácí určité množství kapitálu inflací. Všimněte si, že s-gales a s-supergales jsou příklady supermartingales a 1-gales a 1-supergales jsou přesně martingales a supermartingales.

Společně jsou tyto objekty známé jako „vichřice“.

Vichřice d uspěje na podmnožinu X přirozených čísel, pokud ${displaystyle limsup _ {n} d (X | n) = infty}$ kde ${displaystyle X | n}$ označuje n-místný řetězec skládající se z prvního n číslice X.

Vichřice d silně uspěje na X -li ${displaystyle liminf _ {n} d (X | n) = infty}$.

Všechny tyto představy o různých vichřicích nemají žádný efektivní obsah, ale člověk se musí nutně omezit na malou třídu vichřic, protože lze najít nějakou vichřici, která uspěje na dané sadě. Koneckonců, pokud někdo zná posloupnost mincí předem, je snadné vydělat peníze pouhým sázením na známé výsledky každého flipu. Standardní způsob, jak toho dosáhnout, je vyžadovat, aby vichřice byly buď vypočítatelné, nebo blízké vypočítatelným:

Vichřice d je nazýván konstruktivní, e.e.nebo nižší polopočitatelné pokud jsou čísla ${displaystyle d (sigma)}$ jsou rovnoměrně vlevo - tj. reals (tj. lze je rovnoměrně zapsat jako limit rostoucí počítatelné posloupnosti racionálních hodnot).

The efektivní dimenze Hausdorff množiny přirozených čísel X je ${displaystyle inf {s: mathrm {some c.e.} smathrm {-gale uspělo}} X}}$.^[2]

The efektivní rozměr balení z X je ${displaystyle inf {s: mathrm {some c.e.} smathrm {-gale úspěšně uspěje} X}}$.^[3]

Definice Kolmogorovovy složitosti

Kolmogorovova složitost lze považovat za spodní hranici algoritmické stlačitelnosti konečné posloupnosti (znaků nebo binárních číslic). Přiřadí každé takové posloupnosti w přirozené číslo K (w) který intuitivně měří minimální délku počítačového programu (napsaného v nějakém pevném programovacím jazyce), který nepřijímá žádný vstup a bude na něm w při běhu.

The efektivní dimenze Hausdorff množiny přirozených čísel X je ${displaystyle liminf _ {n} {frac {K (X | n)} {n}}}$.^[4][5][6][7]

The efektivní rozměr balení sady X je ${displaystyle limsup _ {n} {frac {K (X | n)} {n}}}$.^[3][4][5]

Z toho je vidět, že jak efektivní Hausdorffova dimenze, tak efektivní rozměr balení sady jsou mezi 0 a 1, přičemž efektivní rozměr balení je vždy alespoň tak velký jako efektivní Hausdorffův rozměr. Každý náhodná sekvence bude mít efektivní Hausdorff a rozměry balení rovné 1, ačkoli existují i ​​nenáhodné sekvence s účinným Hausdorffem a rozměry balení 1.

Srovnání s klasickým rozměrem

Li Z je podmnožinou 2^ω, jeho Hausdorffova dimenze je ${displaystyle inf {s: mathrm {some} smathrm {-gale uspěje na všech prvcích} Z}}$.^[2]

Rozměr balení Z je ${displaystyle inf {s: mathrm {some} smathrm {-gale silně uspěje ve všech prvcích} Z}}$.^[3]

Tedy efektivní Hausdorff a rozměry balení sady ${displaystyle X}$ jsou prostě klasický Hausdorff a rozměry balení ${displaystyle {X}}$ (respektive), když omezíme naši pozornost na c.e. vichřice.

Definujte následující:

${displaystyle H_ {eta}: = {Xin 2 ^ {omega}: X mathrm {má efektivní Hausdorffovu dimenzi} eta}}$

${displaystyle H_ {leq eta}: = {Xin 2 ^ {omega}: X mathrm {má efektivní Hausdorffovu dimenzi} leq eta}}$

${displaystyle H _ {$

${displaystyle P_ {eta}: = {Xin 2 ^ {omega}: X mathrm {má efektivní dimenzi balení} eta}}$

${displaystyle P_ {leq eta}: = {Xin 2 ^ {omega}: X mathrm {má efektivní rozměr balení} leq eta}}$

${displaystyle P _ {$

Důsledkem výše uvedeného je, že všechny mají Hausdorffovu dimenzi ${displaystyle eta}$.^[8]

${displaystyle H_ {eta}, H_ {leq eta}}$ a ${displaystyle H _ {$ všechny mají rozměr balení 1.

${displaystyle P_ {eta}, P_ {leq eta}}$ a ${displaystyle P _ {$ všechny mají rozměr balení ${displaystyle eta}$.

Reference

• J. H. Lutz (2005). "Efektivní fraktální rozměry". Matematická logika čtvrtletně. 51 (1): 62–72. CiteSeerX  10.1.1.143.7654. doi:10.1002 / malq.200310127. [1]
• J. Reimann (2004). "Vyčíslitelnost a fraktální rozměr, disertační práce". Ruprecht-Karls Universität Heidelberg. Citovat deník vyžaduje | deník = (Pomoc) [2]
• L. Staiger (2007). "Kolmogorovova složitost nekonečných slov". Teoretická informatika. 383 (2–3): 187–199. doi:10.1016 / j.tcs.2007.04.013. [3]