Efektywny wymiar

W matematyce efektywny wymiar jest modyfikacją wymiaru Hausdorffa i innych wymiarów fraktalnych , która umieszcza go w układzie teorii obliczalności . Istnieje kilka odmian (różne pojęcia efektywnego wymiaru), z których najbardziej powszechnym jest efektywny wymiar Hausdorffa . Wymiar w matematyce to szczególny sposób opisywania wielkości obiektu (w przeciwieństwie do miary i innych, odmiennych pojęć wielkości). Wymiar Hausdorffa uogólnia dobrze znane wymiary całkowite przypisane do punktów, linii, płaszczyzn itp., Umożliwiając rozróżnienie obiektów o pośredniej wielkości między tymi obiektami o wymiarach całkowitych. Na przykład fraktalne podzbiory płaszczyzny mogą mieć wymiar pośredni między 1 a 2, ponieważ są „większe” niż linie lub krzywe, a jednocześnie „mniejsze” niż wypełnione koła lub prostokąty. Wymiar efektywny modyfikuje wymiar Hausdorffa, wymagając, aby obiekty o małym wymiarze efektywnym były nie tylko małe, ale także lokalizowalne (lub częściowo lokalizowalne) w sensie obliczeniowym. W związku z tym obiekty o dużym wymiarze Hausdorffa mają również duży wymiar efektywny, a obiekty o małym wymiarze efektywnym mają mały wymiar Hausdorffa, ale obiekt może mieć mały wymiar Hausdorffa, ale duży wymiar efektywny. Przykładem jest algorytmicznie losowy punkt na linii, który ma wymiar Hausdorffa 0 (ponieważ jest to punkt), ale efektywny wymiar 1 (ponieważ, z grubsza mówiąc, nie można go efektywnie zlokalizować lepiej niż mały przedział, który ma Hausdorffa wymiar 1).

Rygorystyczne definicje

W tym artykule zdefiniujemy wymiar efektywny dla podzbiorów przestrzeni Cantora 2 ^ω ; istnieją ściśle powiązane definicje dla podzbiorów przestrzeni euklidesowej R ⁿ . Będziemy swobodnie poruszać się między rozważaniem zbioru X liczb naturalnych, nieskończonego ciągu określonego przez funkcję charakterystyczną X $z$ a liczbą rzeczywistą rozwinięciem binarnym X .

Martingale i inne wichury

Martyngał w przestrzeni Cantora 2 ^ω jest funkcją d : 2 ^ω → R ^{≥ 0 z przestrzeni Cantora do nieujemnych liczb rzeczywistych} , która spełnia warunek słuszności:

${\ Displaystyle d (\ sigma) = {\ Frac {1} {2}} (d (\ sigma 0) + d (\ sigma 1))}$

Martyngał jest uważany za strategię obstawiania, a funkcja daje kapitał lepszego po obejrzeniu sekwencji σ 0 i 1. re $\ displaystyle d (\ sigma)}$ Warunek uczciwości mówi wtedy, że kapitał po sekwencji σ jest średnią kapitału po zobaczeniu σ0 i σ1; innymi słowy martyngał podaje schemat obstawiania dla bukmachera z kursem 2:1 oferowanym na jedną z dwóch „równie prawdopodobnych” opcji, stąd nazwa fair.

(Zauważ, że różni się to nieznacznie od pojęcia martyngału w teorii prawdopodobieństwa. Ta definicja martyngału ma podobny warunek słuszności, który stwierdza również, że wartość oczekiwana po pewnej obserwacji jest taka sama jak wartość przed obserwacją, biorąc pod uwagę wcześniejszą historię Różnica polega na tym, że w teorii prawdopodobieństwa uprzednia historia obserwacji odnosi się po prostu do historii kapitału, podczas gdy tutaj historia odnosi się do dokładnej sekwencji zer i jedynek w łańcuchu.)

Supermartyngał w przestrzeni Cantora to funkcja d jak powyżej , która spełnia zmodyfikowany warunek słuszności:

${\ Displaystyle d (\ sigma) \ geq {\ Frac {1} {2}} (d (\ sigma 0) + d (\ sigma 1))}$

Supermartyngał to strategia obstawiania, w której oczekiwany kapitał po zakładzie jest nie większy niż kapitał przed zakładem, w przeciwieństwie do martyngału, w którym oba są zawsze równe. Pozwala to na większą elastyczność i jest bardzo podobne w przypadku nieefektywnym, ponieważ ilekroć podany jest supermartyngał d , istnieje zmodyfikowana funkcja d' , która wygrywa co najmniej tyle samo pieniędzy co d i która jest w rzeczywistości martyngałem. Jednak warto pozwolić na dodatkową elastyczność, gdy zacznie się mówić o faktycznym dostarczaniu algorytmów do określania strategii obstawiania, ponieważ niektóre algorytmy bardziej naturalnie nadają się do tworzenia supermartyngałów niż martyngałów.

An s - wichura jest funkcją d postaci jak wyżej

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

dla e jakiś martyngał.

S - supergale jest funkcją d jak wyżej postaci

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

dla e jakiś supermartingale.

S- (super)gale to strategia obstawiania, w której na każdym kroku pewna część kapitału jest tracona na skutek inflacji . Zauważ, że s -gale i s -supergale są przykładami supermartyngałów, a 1-gales i 1-supergale to właśnie martyngały i supermartyngały.

Łącznie obiekty te są znane jako „burze”.

Gale d udaje się na podzbiorze X liczb naturalnych, jeśli ${\ Displaystyle \ limsup _ {n} d (X | n) = \ infty}$ gdzie ${\ Displaystyle X | n}$ oznacza n -cyfrowy ciąg składający się z pierwszych n cyfr X .

Wichura d odnosi sukcesy na X , jeśli ${\ Displaystyle \ liminf _ {n} d (X | n) = \ infty}$ .

Wszystkie te pojęcia różnych wichur nie mają skutecznej treści, ale trzeba koniecznie ograniczyć się do małej klasy wichur, ponieważ można znaleźć wichurę, która odnosi sukcesy w dowolnym zbiorze. W końcu, jeśli zna się z góry sekwencję rzutów monetą, łatwo jest zarobić pieniądze, po prostu obstawiając znane wyniki każdego rzutu. Standardowym sposobem na to jest wymaganie, aby wichury były obliczalne lub bliskie obliczalności:

Gale d nazywana jest konstruktywną , ce lub niższą półobliczalną, jeśli liczby są jednolicie lewostronnymi liczbami rzeczywistymi (tj. można je jednolicie zapisać jako granicę $rosnącej$ racjonalistów).

Efektywny $\ Displaystyle \ inf \ {s: \ operatorname {niektóre \ ce} \ s \ operatorname {-gale \ udaje się \ na \} X \$ Hausdorffa zbioru liczb X to .

Efektywny $inf \ {s: \ operatorname {niektóre \ ce} \ s \ operatorname {-gale \ udaje się\ silnie\ na\ } X\}}$ upakowania X to _ .

Definicja złożoności Kołmogorowa

Złożoność Kołmogorowa można traktować jako dolną granicę ściśliwości algorytmicznej skończonej sekwencji (znaków lub cyfr binarnych). Każdemu takiemu ciągowi przypisuje liczbę naturalną K(w) , która intuicyjnie mierzy minimalną długość programu komputerowego (napisanego w jakimś ustalonym języku programowania), który nie pobiera żadnych danych wejściowych i wyświetla wynik w po uruchomieniu.

Efektywny wymiar Hausdorffa zbioru liczb naturalnych X to ${\ Displaystyle \ liminf _ {n} {\ Frac {K (X | n)} {n}}}$ .

Efektywny wymiar pakowania zestawu X to ${\ Displaystyle \ limsup _ {n} {\ frac {K (X | n)} {n}}}$ .

Z tego widać, że zarówno efektywny wymiar Hausdorffa, jak i efektywny wymiar upakowania zestawu mieszczą się w przedziale od 0 do 1, przy czym efektywny wymiar upakowania jest zawsze co najmniej tak duży, jak efektywny wymiar Hausdorffa. Każda sekwencja losowa będzie miała efektywne wymiary Hausdorffa i upakowania równe 1, chociaż istnieją również ciągi nielosowe z efektywnymi wymiarami Hausdorffa i upakowania równymi 1.

Porównanie do wymiaru klasycznego

Jeśli Z jest podzbiorem 2 ^ω , jego wymiar Hausdorffa ${\ Displaystyle \ inf \ {s: \ operatorname {niektóre} \ s \ operatorname {-gale \ udaje się \ na \ wszystkie \ elementy \ \ } Z \}}$ .

Wymiar upakowania Z wynosi ${\ Displaystyle \ inf \ {s: \ operatorname {niektóre} \ s \ operatorname {-gale \ odnosi sukces \ mocno \ na \ wszystkie \ elementy \ z \ } Z \}}$ .

Tak więc efektywny Hausdorff i wymiary opakowania zestawu są po prostu klasycznymi wymiarami Hausdorffa i opakowania $gdy$$),$ naszą uwagę do

Zdefiniuj następujące:

$Displaystyle H _ {\$

${\ Displaystyle H _ {\ równoważnik \ beta}: = \ {X \ w 2 ^ {$

$} <\beta \}}$

$\ Displaystyle H _ {<\ beta}: = \ {X \ w 2 ^ {\ omega}: X \ \ operatorname {ma \ skuteczne \ Hausdorff\ wymiar$

${\ Displaystyle P _ {\ beta}: = \ {X \ w 2 ^ {\ omega}: X \ \ operatorname {ma \ efektywne \ pakowanie \ wymiar \ } \ beta \}} P$

$P _ {\ równoważnik \ beta}: = \ {X\in 2^{\omega }:X\ \mathrm {ma\ efektywne\ opakowanie\ wymiar\ } \leq \beta \}} P$

$\ Displaystyle P _ {<\ beta}: = \ {X \ w 2 ^ {\ omega}: X$

Konsekwencją powyższego jest to, że wszystkie one mają $wymiar$ .

${\ Displaystyle H _ {\ beta}, H _ {\ równoważnik \ beta}}$ i ${\ Displaystyle H_ {<\ beta}}$ wszystkie mają wymiar pakowania 1.

${\ Displaystyle P _ {\ beta}, P _ {\ równoważnik \ beta}}$ i wszystkie mają ${\ Displaystyle$ pakowania $P _ {<\ beta}}$ .

•    JH Lutza (2005). „Efektywne wymiary fraktalne”. Kwartalnik logiki matematycznej . 51 (1): 62–72. CiteSeerX 10.1.1.143.7654 . doi : 10.1002/malq.200310127 . S2CID 206223293 . [1]
• J. Reimanna (2004). „Obliczalność i wymiar fraktalny, praca doktorska”. Ruprecht-Karls Universität Heidelberg. {{ cite journal }} : Cite journal wymaga |journal= ( help ) [2]
• L. Staigera (2007). „Złożoność Kołmogorowa nieskończonych słów” . Informatyka teoretyczna . 383 (2–3): 187–199. doi : 10.1016/j.tcs.2007.04.013 . [3]