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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Буря d сильно преуспевает на Икс если ${displaystyle liminf _{n}d(X|n)=infty }$.

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

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

В эффективное хаусдорфово измерение набора натуральных чисел Икс является ${displaystyle inf{s:mathrm {some c.e.} smathrm {-gale succeeds on } X}}$.^[2]

В эффективный размер упаковки из Икс является ${displaystyle inf{s:mathrm {some c.e.} smathrm {-gale succeeds strongly on } X}}$.^[3]

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

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

В эффективное хаусдорфово измерение набора натуральных чисел Икс является ${displaystyle liminf _{n}{frac {K(X|n)}{n}}}$.^[4][5][6][7]

В эффективный размер упаковки набора Икс является ${displaystyle limsup _{n}{frac {K(X|n)}{n}}}$.^[3][4][5]

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

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

Если Z это подмножество 2^ω, его размерность Хаусдорфа равна ${displaystyle inf{s:mathrm {some} smathrm {-gale succeeds on all elements of } Z}}$.^[2]

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

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

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

${displaystyle H_{eta }:={Xin 2^{omega }:X mathrm {has effective Hausdorff dimension } eta }}$

${displaystyle H_{leq eta }:={Xin 2^{omega }:X mathrm {has effective Hausdorff dimension } leq eta }}$

${displaystyle H_{<eta }:={Xin 2^{omega }:X mathrm {has effective Hausdorff dimension } <eta }}$

${displaystyle P_{eta }:={Xin 2^{omega }:X mathrm {has effective packing dimension } eta }}$

${displaystyle P_{leq eta }:={Xin 2^{omega }:X mathrm {has effective packing dimension } leq eta }}$

${displaystyle P_{<eta }:={Xin 2^{omega }:X mathrm {has effective packing dimension } <eta }}$

Следствием вышесказанного является то, что все они имеют размерность Хаусдорфа. ${displaystyle eta }$.^[8]

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

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

использованная литература

1. Джон М. Хичкок; Джек Х. Лутц (2006). «Почему вычислительная сложность требует более строгих мартингалов». Теория вычислительных систем.
2. Джек Х. Лутц (2003). «Размерность в классах сложности». SIAM Журнал по вычислениям. 32 (5): 1236–1259. arXiv:cs / 0203016. Дои:10.1137 / s0097539701417723.
3. Кришна Б. Атрейя; Джон М. Хичкок; Джек Х. Лутц; Эльвира Майордомо (2007). «Эффективное сильное измерение алгоритмической информации и вычислительной сложности». SIAM Журнал по вычислениям. 37 (3): 671–705. arXiv:cs / 0211025. Дои:10.1137 / s0097539703446912.
4. Цзинь-и Цай; Юрис Хартманис (1994). "О хаусдорфовой и топологической размерности колмогоровской сложности вещественной прямой". Журнал компьютерных и системных наук. 49 (3): 605–619. Дои:10.1016 / S0022-0000 (05) 80073-X.
5. Людвиг Штайгер (1993). «Колмогоровская сложность и хаусдорфова размерность». Информация и вычисления. 103 (2): 159–194. Дои:10.1006 / inco.1993.1017.
6. Эльвира Майордомо (2002). "Характеристика колмогоровской сложности конструктивной хаусдорфовой размерности". Письма об обработке информации. 84: 1–3. Дои:10.1016 / S0020-0190 (02) 00343-5.
7. Людвиг Штайгер (2005). «Конструктивная размерность равна колмогоровской сложности». Письма об обработке информации. 93 (3): 149–153. Дои:10.1016 / j.ipl.2004.09.023.
8. Борис Рябко (1994). «Кодирование комбинаторных источников и размерность Хаусдорфа». Советская математика - Доклады.

• Дж. Х. Лутц (2005). «Эффективные фрактальные размерности». Mathematical Logic Quarterly. 51 (1): 62–72. CiteSeerX  10.1.1.143.7654. Дои:10.1002 / malq.200310127. [1]
• Дж. Рейманн (2004). «Вычислимость и фрактальная размерность, кандидатская диссертация». Ruprecht-Karls Universität Heidelberg. [2]
• Л. Штайгер (2007). «Колмогоровская сложность бесконечных слов». Теоретическая информатика. 383 (2–3): 187–199. Дои:10.1016 / j.tcs.2007.04.013. [3]