Dimensión efectiva

En matemáticas , la dimensión efectiva es una modificación de la dimensión de Hausdorff y otras dimensiones fractales que la coloca en un entorno de teoría de computabilidad . Hay varias variaciones (varias nociones de dimensión efectiva) de las cuales la más común es la dimensión efectiva de Hausdorff . La dimensión , en matemáticas, es una forma particular de describir el tamaño de un objeto (en contraste con la medida y otras nociones de tamaño diferentes). La dimensión de Hausdorff generaliza las conocidas dimensiones enteras asignadas a puntos, líneas, planos, etc. al permitir distinguir entre objetos de tamaño intermedio entre estos objetos de dimensión entera. Por ejemplo, los subconjuntos fractales del plano pueden tener una dimensión intermedia entre 1 y 2, ya que son "más grandes" que las líneas o curvas, y sin embargo "más pequeños" que los círculos o rectángulos rellenos. La dimensión efectiva modifica la dimensión de Hausdorff al requerir que los objetos con una dimensión efectiva pequeña no solo sean pequeños sino también localizables (o parcialmente localizables) en un sentido computable. Por lo tanto, los objetos con una gran dimensión de Hausdorff también tienen una gran dimensión efectiva, y los objetos con una pequeña dimensión efectiva tienen una pequeña dimensión de Hausdorff, pero un objeto puede tener una pequeña dimensión de Hausdorff pero una gran dimensión efectiva. Un ejemplo es un punto aleatorio algorítmicamente en una línea, que tiene una dimensión de Hausdorff 0 (ya que es un punto) pero una dimensión efectiva 1 (porque, en términos generales, no se puede localizar de manera efectiva mejor que un intervalo pequeño, que tiene una dimensión de Hausdorff 1).

Definiciones rigurosas

En este artículo se definirá la dimensión efectiva para los subconjuntos del espacio de Cantor 2 ^ω ; existen definiciones estrechamente relacionadas para los subconjuntos del espacio euclidiano R ⁿ . Nos moveremos libremente entre considerar un conjunto X de números naturales, la secuencia infinita dada por la función característica de X y el número real con expansión binaria 0. X . ${\displaystyle \chi _{X}}$

Martingalas y otros vendavales

Una martingala en el espacio de Cantor 2 ^ω es una función d : 2 ^ω → R ^{≥ 0} del espacio de Cantor a reales no negativos que satisface la condición de equidad:

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

La martingala se considera una estrategia de apuestas, y la función da el capital del mejor después de ver una secuencia σ de 0 y 1. La condición de imparcialidad dice entonces que el capital después de una secuencia σ es el promedio del capital después de ver σ0 y σ1; en otras palabras, la martingala da un esquema de apuestas para un corredor de apuestas con probabilidades de 2:1 ofrecidas en cualquiera de dos opciones "igualmente probables", de ahí el nombre de justa. ${\displaystyle d(\sigma )}$

(Nótese que esto es sutilmente diferente de la noción de teoría de probabilidad de martingala . ^[1] Esa definición de martingala tiene una condición de imparcialidad similar, que también establece que el valor esperado después de alguna observación es el mismo que el valor antes de la observación, dado el historial previo de observaciones. La diferencia es que en la teoría de probabilidad, el historial previo de observaciones solo se refiere al historial de capital, mientras que aquí el historial se refiere a la secuencia exacta de 0 y 1 en la cadena).

Una supermartingala en el espacio de Cantor es una función d como la anterior que satisface una condición de equidad modificada:

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

Una supermartingala es una estrategia de apuestas en la que el capital esperado después de una apuesta no es mayor que el capital antes de la apuesta, en contraste con una martingala, en la que ambos son siempre iguales. Esto permite una mayor flexibilidad y es muy similar en el caso no efectivo, ya que siempre que se da una supermartingala d , existe una función modificada d' que gana al menos tanto dinero como d y que en realidad es una martingala. Sin embargo, es útil permitir la flexibilidad adicional una vez que se empieza a hablar de proporcionar algoritmos para determinar la estrategia de apuestas, ya que algunos algoritmos se prestan de forma más natural a producir supermartingalas que martingalas.

Una s - gale es una función d como la anterior de la forma

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

para e alguna martingala.

Un s - supergale es una función d como la anterior de la forma

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

para e alguna supermartingala.

Un s- (super)gale es una estrategia de apuestas en la que se pierde cierta cantidad de capital debido a la inflación en cada paso. Nótese que los s -gales y los s -supergales son ejemplos de supermartingalas, y los 1-gales y 1-supergales son precisamente las martingalas y supermartingalas.

En conjunto, estos objetos se conocen como "vendavales".

Un vendaval d tiene éxito en un subconjunto X de los números naturales si donde denota la cadena de n dígitos que consiste en los primeros n dígitos de X. ${\displaystyle \limsup _{n}d(X|n)=\infty }$ ${\displaystyle X|n}$

Un vendaval d tiene un fuerte éxito en X si . ${\displaystyle \liminf _{n}d(X|n)=\infty }$

Todas estas nociones de diversos vendavales no tienen contenido efectivo, pero uno necesariamente debe restringirse a una pequeña clase de vendavales, ya que se puede encontrar algún vendaval que tenga éxito en cualquier conjunto dado. Después de todo, si uno conoce una secuencia de lanzamientos de moneda de antemano, es fácil ganar dinero simplemente apostando a los resultados conocidos de cada lanzamiento. Una forma estándar de hacer esto es exigir que los vendavales sean computables o casi computables:

Un gal d se llama constructivo , ce o semicomputable inferior si los números son reales ce-izquierdistas uniformemente (es decir, pueden escribirse uniformemente como el límite de una secuencia computable creciente de racionales). ${\displaystyle d(\sigma )}$

La dimensión efectiva de Hausdorff de un conjunto de números naturales X es . ^[2] ${\displaystyle \inf\{s:\mathrm {some\ c.e.} \ s\mathrm {-gale\ succeeds\ on\ } X\}}$

La dimensión de empaque efectiva de X es . ^[3] ${\displaystyle \inf\{s:\mathrm {some\ c.e.} \ s\mathrm {-gale\ succeeds\ strongly\ on\ } X\}}$

Definición de complejidad de Kolmogorov

La complejidad de Kolmogorov puede considerarse como un límite inferior de la compresibilidad algorítmica de una secuencia finita (de caracteres o dígitos binarios). Asigna a cada una de esas secuencias w un número natural K(w) que, intuitivamente, mide la longitud mínima de un programa informático (escrito en algún lenguaje de programación fijo) que no requiere ninguna entrada y que generará w cuando se ejecute.

La dimensión efectiva de Hausdorff de un conjunto de números naturales X es . ^{[4] [5] [6] [7]} ${\displaystyle \liminf _{n}{\frac {K(X|n)}{n}}}$

La dimensión de empaquetamiento efectiva de un conjunto X es . ^{[3] [4] [5]} ${\displaystyle \limsup _{n}{\frac {K(X|n)}{n}}}$

De esto se desprende que tanto la dimensión efectiva de Hausdorff como la dimensión efectiva de empaquetamiento de un conjunto están entre 0 y 1, siendo la dimensión efectiva de empaquetamiento siempre al menos tan grande como la dimensión efectiva de Hausdorff. Toda secuencia aleatoria tendrá dimensiones efectivas de Hausdorff y empaquetamiento iguales a 1, aunque también existen secuencias no aleatorias con dimensiones efectivas de Hausdorff y empaquetamiento de 1.

Comparación con la dimensión clásica

Si Z es un subconjunto de 2 ^ω , su dimensión de Hausdorff es . ^[2] ${\displaystyle \inf\{s:\mathrm {some} \ s\mathrm {-gale\ succeeds\ on\ all\ elements\ of\ } Z\}}$

La dimensión de empaquetamiento de Z es . ^[3] ${\displaystyle \inf\{s:\mathrm {some} \ s\mathrm {-gale\ succeeds\ strongly\ on\ all\ elements\ of\ } Z\}}$

Por lo tanto, las dimensiones efectivas de Hausdorff y de empaquetamiento de un conjunto son simplemente las dimensiones clásicas de Hausdorff y de empaquetamiento de (respectivamente) cuando restringimos nuestra atención a los gales ce. ${\displaystyle X}$ ${\displaystyle \{X\}}$

Defina lo siguiente:

${\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 \}}$

Una consecuencia de lo anterior es que todos ellos tienen dimensión de Hausdorff . ^[8] ${\displaystyle \beta }$

${\displaystyle H_{\beta },H_{\leq \beta }}$y todos tienen dimensión de embalaje 1. ${\displaystyle H_{<\beta }}$

${\displaystyle P_{\beta },P_{\leq \beta }}$y todos tienen dimensiones de embalaje . ${\displaystyle P_{<\beta }}$ ${\displaystyle \beta }$

Referencias

1. John M. Hitchcock; Jack H. Lutz (2006). "Por qué la complejidad computacional requiere martingalas más estrictas". Teoría de los sistemas informáticos .
2. Jack H. Lutz (2003). "Dimensión en clases de complejidad". Revista SIAM de Computación . 32 (5): 1236–1259. arXiv : cs/0203016 . doi :10.1137/s0097539701417723.
3. Krishna B. Athreya; John M. Hitchcock; Jack H. Lutz; Elvira Mayordomo (2007). "Dimensión fuerte efectiva en información algorítmica y complejidad computacional". Revista SIAM de Computación . 37 (3): 671–705. arXiv : cs/0211025 . doi :10.1137/s0097539703446912. S2CID  27038.
4. Jin-yi Cai; Juris Hartmanis (1994). "Sobre las dimensiones topológicas y de Hausdorff de la complejidad de Kolmogorov de la línea real". Revista de Ciencias de la Computación y de Sistemas . 49 (3): 605–619. doi : 10.1016/S0022-0000(05)80073-X .
5. Ludwig Staiger (1993). "Complejidad de Kolmogorov y dimensión de Hausdorff". Información y Computación . 103 (2): 159-194. doi : 10.1006/inco.1993.1017 .
6. Elvira Mayordomo (2002). "Una caracterización de la complejidad de Kolmogorov de la dimensión constructiva de Hausdorff". Information Processing Letters . 84 : 1–3. doi :10.1016/S0020-0190(02)00343-5.
7. Ludwig Staiger (2005). "La dimensión constructiva equivale a la complejidad de Kolmogorov". Information Processing Letters . 93 (3): 149–153. doi :10.1016/j.ipl.2004.09.023. hdl : 2292/3717 .
8. Boris Ryabko (1994). "Codificación de fuentes combinatorias y dimensión de Hausdorff". Matemáticas soviéticas - Doklady .