Поиск

Карта → событие

Париж диссертация — 1939

Вилль: коллектив опровергнут, появляется мартингал

Теория вероятностей Демон и монетка

Определение фон Мизеса починили дважды и решили, что оно устояло. В 1939 году Жан Вилль защитил в Париже диссертацию, которая его добила, — и на месте разрушенного оставил понятие, живущее до сих пор.

Как именно оно рухнуло

Вилль не стал доказывать, что коллективов не существует: после Вальда было известно, что существуют. Он доказал обратное и худшее.

Теорема Вилля. Каков бы ни был счётный набор правил выбора, найдётся последовательность, которая по отношению ко всем этим правилам является коллективом с $p = 1/2$ — и при этом

$$\frac{k_n}{n} \;\geqslant\; \frac{1}{2} \qquad \text{для всех } n .$$

То есть доля единиц подходит к своему пределу всё время сверху, ни разу не опускаясь ниже половины.

Почему это приговор

Настоящая случайная последовательность так себя не ведёт, и это давно посчитано. Закон повторного логарифма (ХинчинАлександр Яковлевич Хинчинсоветский математик · 1894–1959Дал теории случайных процессов язык, на котором с тех пор говорят обработка сигналов и анализ временных рядов, — и написал книгу, в которой теоремы Шеннона впервые доказаны математически строго., 1924) говорит: если $\varepsilon_i = \pm 1$ — честные независимые знаки, то с вероятностью $1$

$$\limsup_{n\to\infty} \frac{\varepsilon_1 + \dots + \varepsilon_n}{\sqrt{2n\ln\ln n}} = 1, \qquad \liminf_{n\to\infty} \frac{\varepsilon_1 + \dots + \varepsilon_n}{\sqrt{2n\ln\ln n}} = -1 .$$

+1−10отклонение числа единиц от половины, нормированноезакон повторного логарифма держит его между −1 и +1границы закона повторного логарифмаПять честных реализаций (тонкие): вместе переходят через ноль 68 раз — то вверх, то внизПоследовательность Вилля (жирная) не опускается ниже нуля ни разу: так она устроенаИ при этом удовлетворяет всем правилам выбора — уличить её выбором розыгрышей нельзя
Честная последовательность переходит через половину бесконечно много раз и держится в границах закона повторного логарифма. Последовательность Вилля не опускается ниже половины никогда — и всем правилам выбора при этом удовлетворяетMathLocus · построено для этого сайта

Перевес обязан бесконечно много раз переходить через ноль в обе стороны, и притом с точно известным размахом. Последовательность Вилля этого не делает никогда. Она проваливает совершенно обычную статистическую проверку — и всё-таки удовлетворяет определению.

Диагноз точный: правило выбора видит только, на что ставить, но не видит, сколько ставить. Игрок, которому разрешено лишь пропускать розыгрыши, слишком слаб, чтобы поймать всё неслучайное.

Мартингал: ставка вместо выбора

Вилль усиливает игрока. Пусть у него капитал $V_0 = 1$, и перед каждым знаком он делит капитал между «выпадет 0» и «выпадет 1» как хочет. Игра честная, значит

$$V_n \;=\; \frac{V_{n+1}(\text{если }0) + V_{n+1}(\text{если }1)}{2} .$$

Такая последовательность капиталов и называется мартингалом. Правило выбора — её частный случай: ставить всё или не ставить ничего. Дробные ставки строго сильнее.

Определение Вилля: последовательность случайна, если никакая стратегия из разрешённого класса не делает капитал неограниченным.

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

Это в точности тот мост, по которому через двадцать семь лет пойдёт Мартин-Лёф: у него случайность определяется через множества меры нуль, и совпадение с определением Вилля не случайно, а доказано.

Для класса

Слово «мартингал» до Вилля означало систему игры: проигрался — удвой ставку.

  1. Игрок ставит 1 рубль на красное. Проиграл — ставит 2, снова проиграл — 4, и так далее. Сколько денег нужно иметь, чтобы пережить $k$ проигрышей подряд? Сколько он выигрывает, когда наконец выпадает красное?
  2. Вероятность красного на рулетке с зеро — $18/37$. Найдите вероятность того, что игрок с капиталом $2^{10}-1$ рублей разорится, не дождавшись выигрыша.
  3. Посчитайте математическое ожидание выигрыша за одну такую серию — с учётом разорения. Сравните с нулём и объясните, почему «верная система» верной не является.
  4. А теперь честная монета вместо рулетки. Ожидание стало нулевым — значит ли это, что система работает? (Подсказка: посмотрите, что происходит с капиталом, когда он ограничен сверху и снизу.)

Что стало со словом

Слово родилось в Провансе (по одной из версий — от названия городка Мартиг) и означало ту самую систему удвоения. Вилль взял бытовое слово в математику, Дуб в 1953 году построил на нём целую теорию, и сегодня мартингал — одно из главных понятий теории случайных процессов: на нём стоит и стохастическое исчисление, и формула цены опциона.

Ирония в том, что понятие, названное в честь беспроигрышной системы, служит теперь строгим доказательством того, что беспроигрышных систем не бывает.

О человеке

Жан-Андре Вилль (1910–1989) учился у Мориса ФрешеМорис Фрешефранцузский математик · 1878–1973В диссертации 1906 года определил расстояние там, где нет чисел, — и превратил «близость» в отдельный предмет, из которого выросли метрические пространства и общая топология.. Ещё до диссертации, в 1938 году, он дал первое элементарное доказательство теоремы о минимаксе — того самого результата фон НейманаДжон фон Нейманвенгеро-американский математик · 1903–1957Аксиоматизировал квантовую механику, основал теорию игр, придумал архитектуру компьютера и метод Монте-Карло — и всё это, по мнению современников, не напрягаясь., на котором стоит теория игр. После войны занимался математической экономикой и эконометрикой, был профессором в Париже. Диссертация 1939 года, разрушившая программу фон Мизеса, оставалась почти незамеченной тридцать лет — пока алгоритмическая теория случайности не подобрала из неё мартингал и не построила на нём третью, вычислительную линию определений.

Открыть на карте