Вопрос тут был вполне естественный — но я расскажу сначала его упрощённую версию.
Можно спрашивать, как себя ведут типичные точки отрезка. Но тут ответ простой — если считать 0 и 1 в двоичной записи случайной точки отрезка, то для типичной точки их будет примерно поровну.
А можно спросить, какая размерность множества тех точек, у которых доля единиц в первых n цифрах стремится к заданному p, 0<p<1. И как эта размерность зависит от p.
Можно спрашивать, как себя ведут типичные точки отрезка. Но тут ответ простой — если считать 0 и 1 в двоичной записи случайной точки отрезка, то для типичной точки их будет примерно поровну.
А можно спросить, какая размерность множества тех точек, у которых доля единиц в первых n цифрах стремится к заданному p, 0<p<1. И как эта размерность зависит от p.
Конечно, сразу возникает вопрос, что такое "размерность" — и если отвечать строго, то нужно сказать, что это _хаусдорфова размерность_:
если есть покрытие множества X (бесконечным) объединением шаров радиусов r_j, то его d-мерным объёмом называется сумма ряда из (r_j)^d.
Хаусдорфова размерность множества — инфимум таких d, для которых существуют покрытия со сколь угодно малым d-мерным объёмом.
если есть покрытие множества X (бесконечным) объединением шаров радиусов r_j, то его d-мерным объёмом называется сумма ряда из (r_j)^d.
Хаусдорфова размерность множества — инфимум таких d, для которых существуют покрытия со сколь угодно малым d-мерным объёмом.
(Пара слов об этом написана в конце дубнинской брошюры Ильяшенко — https://www.mccme.ru/dubna/books/pdf/ilyashenko-attr.pdf )
Но можно пока о строгом определении не задумываться и подменить вопрос: зафиксировать большое n и посмотреть на те точки, у которых среди первых n цифр доля единиц уже (примерно) p. Например, у которых единиц ровно m=[pn].
Это будет объединение скольки-то отрезков длины 2^(-n) — если мы совсем зафиксировали число единиц, то их количество это биномиальный коэффициент C_n^m.
Это будет объединение скольки-то отрезков длины 2^(-n) — если мы совсем зафиксировали число единиц, то их количество это биномиальный коэффициент C_n^m.
Соответственно, если мы думаем в терминах размерности — то правильно посмотреть, как какая степень от размера растёт количество этих отрезков. (Отрезок покрывается сотней отрезков длины 1/100, квадрат — 100^2 квадратов со стороной 1/100, d-мерный куб — 100^d кубиками со стороной 1/100.)
То есть нужно посмотреть на отношение
log_2 (C_n^m) / n
log_2 (C_n^m) / n
Формула Стирлинга (потрясающе полезная, которую надо помнить обязательно) говорит, что
n! ~ \sqrt{2 \pi n} (n/e)^n.
n! ~ \sqrt{2 \pi n} (n/e)^n.
Нам тут понадобится только последний сомножитель, экспоненциальный (всё остальное слишком медленное относительно логарифма). Ну и в выражении
C_n^m = n!/(m! (n-m)!)
степени e в числителе и знаменателе сокращаются, и остаётся от экспоненциальной части только
(n/m)^m (n/(n-m))^(n-m).
C_n^m = n!/(m! (n-m)!)
степени e в числителе и знаменателе сокращаются, и остаётся от экспоненциальной части только
(n/m)^m (n/(n-m))^(n-m).
Если прологарифмировать, поделить на n и сказать, что m~np, то получается примерно
(1/n) log_2 C_n^m ~ -p log_2 p - (1-p) log_2 (1-p).
(1/n) log_2 C_n^m ~ -p log_2 p - (1-p) log_2 (1-p).
С одной стороны, вот она размерность. Мы её и правда нашли (хотя, конечно, всё вышесказанное нужно делать честно, а не как я сейчас).
И этим занимался Безикович — тот самый, который решил задачу Какейя о развороте отрезка: что есть (невыпуклая) фигура сколь угодно малой площади, внутри которой можно развернуть отрезок.
(У Марка на слайде в знаменателе логарифм 3, а не логарифм 2 — потому что он вместо отрезка работает с канторовым множеством: его точки тоже можно закодировать 0 и 1, или 0 и 2 — просто взяв троичную запись.)
Математические байки
И этим занимался Безикович — тот самый, который решил задачу Какейя о развороте отрезка: что есть (невыпуклая) фигура сколь угодно малой площади, внутри которой можно развернуть отрезок.
(Да, в качестве отступления в сторону — об этой задаче и конструкции можно прочитать в Кванте —
http://kvant.mccme.ru/1973/04/o_vrashchenii_otrezka.htm )
http://kvant.mccme.ru/1973/04/o_vrashchenii_otrezka.htm )
Математические байки
С одной стороны, вот она размерность. Мы её и правда нашли (хотя, конечно, всё вышесказанное нужно делать честно, а не как я сейчас).
Так вот — с другой стороны, тут появляется выражение (-p log p), которое кому-то может быть знакомо из физики, а кому-то из информатики.
И мне в этом месте хочется сказать слова "энтропия Шеннона".
Представим себе, что на Марсе у нас стоит марсоход, и каждую секунду что-то измеряет. Например, ловит космические лучи — таким образом, разные измерения независимы друг от друга. Но шанс, что что-то прилетит, очень маленький, поэтому таблица из 0 и 1 (не прилетело/прилетело) состоит в основном из нулей, вероятность p единицы очень маленькая.
Как нам передать результаты наблюдений на Землю?
Представим себе, что на Марсе у нас стоит марсоход, и каждую секунду что-то измеряет. Например, ловит космические лучи — таким образом, разные измерения независимы друг от друга. Но шанс, что что-то прилетит, очень маленький, поэтому таблица из 0 и 1 (не прилетело/прилетело) состоит в основном из нулей, вероятность p единицы очень маленькая.
Как нам передать результаты наблюдений на Землю?
Можно, конечно, так и передать, нулями и единицами, но странно забивать канал нулями.
Так вот — при большом числе наблюдений нам понадобится примерно (-p log p - (1-p) log (1-p)) бит в расчёте на одно измерение, чтобы (честно) передать результаты.
Проще всего это сделать так — если мы провели n измерений, то сначала передаём m — число единиц. На это нам нужно log_2(n) бит, что по сравнению с n — копейки.
Теперь, когда мы знаем число единиц — у нас есть C_n^m разных вариантов, и на самом деле, они все равновероятны. Поэтому понятно, что меньше, чем log_2 (C_n^m) битами, мы не обойдёмся. А чтобы передать за это число бит — например, можно (мысленно) лексикографически упорядочить все C_n^m последовательностей из m единиц и (n-m) нулей, и заметить, что соответствие между номером последовательности и самой последовательностью несложно вычисляется в обе стороны.