Эффективный размер

В математике , эффективная размерность — это модификация размерности Хаусдорфа и других фрактальных измерений которая помещает ее в рамки теории вычислимости . Существует несколько вариаций (различные понятия эффективной размерности), из которых наиболее распространенной является эффективная размерность Хаусдорфа . Размерность в математике — это особый способ описания размера объекта (в отличие от меры и других, различных понятий размера). Размерность Хаусдорфа обобщает известные целочисленные размерности, присвоенные точкам, линиям, плоскостям и т. д., позволяя различать объекты промежуточного размера между этими целочисленными объектами. Например, фрактальные подмножества плоскости могут иметь промежуточную размерность между 1 и 2, поскольку они «больше», чем линии или кривые, и все же «меньше», чем закрашенные круги или прямоугольники. Эффективная размерность модифицирует размерность Хаусдорфа, требуя, чтобы объекты с небольшой эффективной размерностью были не только небольшими, но и локализуемыми (или частично локализуемыми) в вычислимом смысле. Таким образом, объекты с большой размерностью Хаусдорфа также имеют большой эффективный размер, а объекты с малым эффективным размером имеют малую размерность Хаусдорфа, но объект может иметь небольшой размер Хаусдорфа, но большой эффективный размер. Примером является алгоритмически случайная точка на прямой, которая имеет размерность Хаусдорфа 0 (поскольку это точка), но эффективную размерность 1 (потому что, грубо говоря, ее невозможно эффективно локализовать лучше, чем небольшой интервал, размерность которого имеет размерность Хаусдорфа 1).

Строгие определения

В этой статье будет определена эффективная размерность подмножеств канторового пространства 2. ^ой ; существуют тесно связанные определения для подмножеств евклидова пространства R ^н . Мы будем свободно перемещаться между рассмотрением множества X натуральных чисел, бесконечной последовательности $\chi _{X}$ задается характеристической функцией X и действительным числом с двоичным представлением 0. X .

Мартингалы и другие штормы

Мартингейл 2 пространстве в канторовом ^ой является функцией d : 2 ^ой → Р ^≥ 0 от канторова пространства к неотрицательным действительным числам, удовлетворяющим условию справедливости:

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

Мартингейл рассматривается как стратегия ставок, а функция $d(\sigma )$ дает лучший капитал после просмотра последовательности σ из 0 и 1. Тогда условие справедливости гласит, что капитал после последовательности σ является средним значением капитала после просмотра σ0 и σ1; Другими словами, мартингейл предлагает схему ставок для букмекера с коэффициентами 2:1, предлагаемыми на любой из двух «равновероятных» вариантов, отсюда и название «справедливый».

(Обратите внимание, что это слегка отличается от понятия мартингала из теории вероятностей . Это определение мартингейла имеет аналогичное условие справедливости, которое также гласит, что ожидаемое значение после некоторого наблюдения такое же, как и значение до наблюдения, учитывая предыдущую историю наблюдений. Разница в том, что в теории вероятностей предыстория наблюдений относится просто к истории капитала, тогда как здесь история относится к точной последовательности нулей и единиц в строке.)

Супермартингал в канторовом пространстве — это функция d , указанная выше, которая удовлетворяет модифицированному условию справедливости:

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

Супермартингейл — это стратегия ставок, в которой ожидаемый капитал после ставки не превышает капитала до ставки, в отличие от мартингейла, где они всегда равны. Это обеспечивает большую гибкость и очень похоже на неэффективный случай, поскольку всякий раз, когда дается супермартингал d , существует модифицированная функция d' , которая выигрывает по крайней мере столько же денег, что и d , и которая на самом деле является мартингейлом. Однако полезно обеспечить дополнительную гибкость, как только мы начнем говорить о фактическом предоставлении алгоритмов для определения стратегии ставок, поскольку некоторые алгоритмы более естественно подходят для создания супермартингалов, чем мартингалов.

S как - шторм - это функция d, указано выше, вида

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

для e немного мартингейла.

s как - супергейл - это функция d, указано выше, вида

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

за какой -нибудь супермартингейл.

Супер- шторм « » — это стратегия ставок, при которой некоторая сумма капитала теряется из-за инфляции на каждом этапе. Обратите внимание, что s -штормы и s -супергалы являются примерами супермартингалов, а 1-штормы и 1-супергалы — это именно мартингалы и супермартингалы.

В совокупности эти объекты известны как «ураганы».

Буря d успешна на подмножестве X натуральных чисел, если $\limsup _{n}d(X|n)=\infty$ где $X|n$ обозначает строку из n цифр, состоящую из первых n цифр X .

Буря d сильно успешна на X, если $\liminf _{n}d(X|n)=\infty$.

Все эти представления о различных штормах не имеют эффективного содержания, но необходимо обязательно ограничиться небольшим классом штормов, поскольку можно найти такой шторм, который будет успешным на любом заданном множестве. В конце концов, если заранее известна последовательность подбрасываний монеты, можно легко заработать деньги, просто делая ставки на известные результаты каждого подбрасывания. Стандартный способ сделать это — потребовать, чтобы штормы были либо вычислимыми, либо близкими к вычислимым:

Буря d называется конструктивной , ce или полувычислимой снизу, если числа $d(\sigma )$ являются равномерно левыми числами (т.е. могут быть равномерно записаны как предел возрастающей вычислимой последовательности рациональных чисел).

Эффективная хаусдорфова размерность набора натуральных чисел X равна $\inf\{s:\mathrm {some\ c.e.} \ s\mathrm {-gale\ succeeds\ on\ } X\}$.

Эффективный упаковки X равен размер $\inf\{s:\mathrm {some\ c.e.} \ s\mathrm {-gale\ succeeds\ strongly\ on\ } X\}$.

Определение колмогоровской сложности

Колмогоровскую сложность можно рассматривать как нижнюю границу алгоритмической сжимаемости конечной последовательности (символов или двоичных цифр). присваивается Каждой такой последовательности w натуральное число K(w), которое интуитивно измеряет минимальную длину компьютерной программы (написанной на каком-то фиксированном языке программирования), которая не принимает никаких входных данных и выводит w при запуске.

Эффективная хаусдорфова размерность набора натуральных чисел X равна $\liminf _{n}{\frac {K(X|n)}{n}}$.

Эффективная размерность упаковки набора X равна $\limsup _{n}{\frac {K(X|n)}{n}}$.

Отсюда видно, что как эффективная размерность Хаусдорфа, так и эффективная размерность упаковки множества находятся в диапазоне от 0 до 1, при этом эффективная размерность упаковки всегда не меньше эффективной размерности Хаусдорфа. Каждая случайная последовательность будет иметь эффективную Хаусдорфову размерность и размерность упаковки, равную 1, хотя существуют также неслучайные последовательности с эффективной Хаусдорфовой размерностью и размерностью упаковки, равной 1.

Сравнение с классическим размером

Если Z является подмножеством 2 ^ой , его хаусдорфова размерность равна $\inf\{s:\mathrm {some} \ s\mathrm {-gale\ succeeds\ on\ all\ elements\ of\ } Z\}$.

Размер упаковки Z составляет $\inf\{s:\mathrm {some} \ s\mathrm {-gale\ succeeds\ strongly\ on\ all\ elements\ of\ } Z\}$.

Таким образом, эффективный Хаусдорф и размеры упаковки множества $X$ — это просто классические размеры Хаусдорфа и упаковки $\{X\}$ (соответственно), когда мы ограничиваем наше внимание ураганами.

Определите следующее:

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

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

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

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

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

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

Следствием вышесказанного является то, что все они имеют размерность Хаусдорфа. $\beta$.

$H_{\beta },H_{\leq \beta }$ и $H_{<\beta }$ все имеют размер упаковки 1.

$P_{\beta },P_{\leq \beta }$ и $P_{<\beta }$ все имеют размер упаковки $\beta$.