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

В статье использованы источники одной исследовательской группы. Соответствующее обсуждение можно найти на страница обсуждения. Пожалуйста помоги улучшить эту статью путем введения цитаты к дополнительным источникам. Найдите источники: «Эффективное измерение» – Новости · газеты · книги · ученый · JSTOR (Ноябрь 2013)

В математика, эффективное измерение это модификация Хаусдорфово измерение и другие фрактальные измерения что помещает его в теория вычислимости настройка. Существует несколько вариантов (различные понятия эффективной размерности), наиболее распространенной из которых является эффективное хаусдорфово измерение. Размерв математике - это особый способ описания размера объекта (в отличие от меры и других, различных понятий размера). Измерение Хаусдорфа обобщает хорошо известные целочисленные измерения, присвоенные точкам, линиям, плоскостям и т. Д., Позволяя различать объекты промежуточного размера между этими целочисленными объектами. Например, фрактал подмножества плоскости могут иметь промежуточный размер от 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 успешно завершается} X}}$.^[2]

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

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

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

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

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

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

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

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

Размер упаковки Z является ${displaystyle inf {s: mathrm {some} smathrm {-gale успешно работает со всеми элементами} Z}}$.^[3]

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

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

${displaystyle H_ {eta}: = {Xin 2 ^ {omega}: X mathrm {имеет эффективное измерение Хаусдорфа} eta}}$

${displaystyle H_ {leq eta}: = {Xin 2 ^ {omega}: X mathrm {имеет эффективное хаусдорфово измерение} leq eta}}$

${displaystyle H _ {$

${displaystyle P_ {eta}: = {Xin 2 ^ {omega}: X mathrm {имеет эффективное измерение упаковки} eta}}$

${displaystyle P_ {leq eta}: = {Xin 2 ^ {omega}: X mathrm {имеет эффективный размер упаковки} leq eta}}$

${displaystyle P _ {$

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

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

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

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

• Дж. Х. Лутц (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]