Регрессия к среднему и ошибка игрока

[sergey zhukov]

Someone в сообщении #1545311 писал(а):

О флуктуациях при бросании монеты интересно написано в книге
В. Феллер. Введение в теорию вероятностей и её приложения. В 2-х томах. Том 1. Москва, "Мир", 1984.

Да, в этой книжке рассматривается такая задача: идет голосование на выборах из двух кандидатов А и В, (причем каждый голосующий с равной вероятностью может проголосовать за любого из двух). Допустим, в итоге победил А. Насколько вероятно, что в течении всего процесса голосования А опережал В, т.е. никогда не отдавал лидерство?
Это кажется маловероятным, т.к. кандидаты по условию одинаково сильны и вроде бы должны "перетягивать канат" туда-сюда. Перевес должен быть то на одной, то на другой стороне. Победа должна переходить от одного к другому каким-то регулярным образом. Не должно быть так, чтобы один из кандидатов все время уверенно побеждал. Ясно, что эта задача о случайных блужданиях монетки и вероятности ее возвращения к нулю.

Между тем, если победил А, то не просто маловероятно, а как раз наиболее вероятно, что он и держался впереди на протяжении всех выборов. Я проверил это утверждение численно на числе голосующих, равном 3000 (повторяя это голосование многократно, конечно). Получилось следующее:


Вероятность того, что в ходе голосования кандидаты менялись лидерством $N$ раз, монотонно падает с увеличением $N$. Вероятнее всего, что они не менялись ни разу.

Интересно, что вероятность того, что первая смена лидерства произойдет на шаге $M$ голосования, очень быстро падает с ростом $M$ ($M=0$ значит, что лидерство не поменялось до конца выборов). В данном примере с 3000 человек получается, что вероятность непрерывно удерживать лидерство на протяжении первых 15 голосующих такая же, как и вероятность непрерывно удерживать лидерство вообще до конца голосования (т.е. даже не просто победить на выборах, а именно быть непрерывным лидером до конца голосования). Т.е. если ты сразу вырвался вперед, то можешь быть спокоен (если ваши силы равны, конечно). Это показывает, что не только вероятность вернуться в ноль $N$ раз за все время голосования падает с ростом $N$, так еще и практически все возвраты вероятнее всего приходятся на начальные шаги.

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

[ipgmvq]

sergey zhukov
Не знаю, что показывает точно большой график, но график в правом верхнем углу как раз говорит о том, что вероятность пересечения нуля (вероятно с любой стороны) уже со вторым голосом составляет 50% (0,5).
Что неудивительно:
при первом голосе 0,5 вероятность, что он будет за А и 0,5 что за B
при втором голосе: при первом за А вероятность 0,5, что он будет за B, и при первом за B вероятность 0,5, что он будет за A. Таким образом, баланс голосов вернется в "ноль" уже со вторым голосом с вероятностью

$0,5 \times 0,5 + 0,5 \times 0,5 = 0,5$

В симуляции условная вероятность всегда удерживать лидерство при победе А тоже в районе 1,5%.

Используется синтаксис Python

import numpy as np
rng = np.random.default_rng()
избирателей = 3000
повторов = 100000
выборка = rng.integers(2, size=(избирателей, повторов)) * 2 - 1
выборка = выборка.cumsum(axis=0)
победители = выборка[избирателей-1,:] > 0
print("Вероятность нелидировать на протяжении всего голосования = %.3f%%" % (100.0 * (np.count_nonzero(выборка[:, победители]==0, axis=0) != 0).sum() / победители.sum()))
 

[mihaild]

sergey zhukov в сообщении #1545893 писал(а):

Вероятнее всего, что они не менялись ни разу.

Это утверждение можно воспринимать как "для любого $n > 0$, ровно 0 смен вероятнее чем ровно $n$ смен" - тогда оно верно, и как "ровно 0 смен вероятнее чем хотя бы одна смена" - и тогда оно неверно.

При $m$ голосующих, в среднем лидер поменяется примерно $\frac{\sqrt m}{2}$ раз.

[ipgmvq]

mihaild в сообщении #1545909 писал(а):

поменяется примерно $\frac{\sqrt m}{2}$ раз

Вероятно $\sqrt \frac{m}{2}$ раз. Очень примерно.

Используется синтаксис Python

import numpy as np
import pandas as pd
rng = np.random.default_rng()
повторов = 10000
средние = list()

for избирателей in [3**i for i in range(10)]:
    выборка = rng.integers(2, size=(избирателей, повторов)) * 2 - 1
    выборка = выборка.cumsum(axis=0)
    средние.append((np.count_nonzero(выборка == 0, axis=0)).mean())

средние = np.array(средние)
индекс = np.array([3**i for i in range(10)])

зависимость = pd.DataFrame({ 'Монте-Карло' : средние, 'Теоретически' : np.sqrt((индекс) / 2.0) }, index = индекс)
print(зависимость)
 

[ozheredov]

(ipgmvq)

ipgmvq
В Пайтон по-русски можно называть переменные?

[ipgmvq]

mihaild в сообщении #1545909 писал(а):

"для любого $n > 0$, ровно 0 смен вероятнее чем ровно $n$ смен" - тогда оно верно

Например, при 3-х и 4-х голосующих вероятность нуля смен равняется вероятности 1 смены, если под сменой понимать в т.ч. возврат старого победителя (т.е. задевание нуля).

ipgmvq в сообщении #1545917 писал(а):

Вероятно $\sqrt \frac{m}{2}$ раз

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

Используется синтаксис Python

import numpy as np
import pandas as pd
rng = np.random.default_rng()

повторов = 1000
средние = list()
паттерн1 = np.array([-1, 0, 1]).reshape((3,1))
паттерн2 = np.array([1, 0, -1]).reshape((3,1))

for избирателей in [3**i for i in range(1, 10)]:
    выборка = rng.integers(2, size=(избирателей, повторов)) * 2 - 1
    выборка = выборка.cumsum(axis=0)
    накопление = np.zeros(shape=(повторов,), dtype=np.int64)
    for j in range(избирателей - 2):
        пат1 = np.all(выборка[j:(j+3),:] == паттерн1, axis=0)
        пат2 = np.all(выборка[j:(j+3),:] == паттерн2, axis=0)
        накопление = накопление + (пат1 | пат2) * 1
    средние.append(накопление.mean())

средние = np.array(средние)
индекс = np.array([3**i for i in range(1, 10)])

зависимость = pd.DataFrame({ 'Пересечения Монте-Карло' : средние, 'Теоретически' : np.sqrt(индекс) / 2.0 }, index = индекс)
print(зависимость)
 

(Оффтоп)

ozheredov
Конечно. Хоть иероглифами или эмоджи. Токенами в Питон являются строки из символов юникода

[mihaild]

Да, это я что-то не то написал. Ожидание числа доходов до нуля - примерно $\sqrt{n}$ (точно - для $2m$ и $2m + 1$ шагов $\frac{C_{2m}^m \cdot (2m + 1)}{2^{2m}} - 1$), но просто так получить из него число смен делением на 2 нельзя.

[sergey zhukov]

mihaild
Да, тут я неправильно сказал. Мода возврата в ноль равна нулю, а матожидание возврата в ноль конечно больше. Численно оно получилось равным 44. Ноль возвратов вероятнее любого другого числа возвратов по отдельности, но гораздо менее вероятен суммы вероятностей всех альтернативных вариантов. Поэтому ожидать отсутствия возвратов вообще не стоит.

Интересно, что условие "$A$ победил с отрывом $M$ голосов" уже просто значит, что у $A$ на $M$ больше сторонников, чем у $B$. Т.е. они по условию не равны. Случайно выбранный человек вероятнее окажется сторонником $A$, чем $B$. Аналогично с условием "$A$ победил с любым отрывом (т.е. с любым $M$ в пределах $0...N$)".

Задача сводится только в тому, чтобы рассмотреть все возможные очереди, в которые может выстроится народ, пришедший голосовать. Но про него заранее известно, что он на стороне $A$. Т.е. на самом деле исходное условие таково, что каждый человек голосует за $A$ с бОльшей вероятностью, чем за $B$. В таком случае нет ничего удивительного, что $A$ вероятнее всего побеждает на протяжении всего голосования. Это блуждания несимметричной монеты.

Что же касается блужданий симметричной монеты. Для 3000 бросков плотность вероятности возвратов в ноль получается такой:


Эта кривая $\sim \frac{1}{\sqrt{n}}$. Плотность вероятности появления точек возврата в ноль с течением времени уменьшается, но медленно. Например, медиана этого распределения есть 780 шагов. Это совсем не мало в сравнении с 3000, т.е. нельзя сказать, что все достижения нуля сосредоточены в самом начале пути, т.е. лидер определяется "в первые минуты".

Хотя, если известно, что на шаге $n$ $A$ уже побеждает $B$ на $M$ голосов, то это равносильно тому, что голосование стартует заново из точки $(n;0)$, но теперь каждый пришедший голосует несимметрично в пользу $A$. Так что случайное начальное преимущество $M$ равносильно тому, что голосование начинается сначала при условии голосования в среднем в пользу $A$. При таких условиях $A$ вероятнее всего снова получит преимущество, а $B$ - не получит. Поэтому плотность достижения нулевых точек падает с течением времени.

[ipgmvq]

mihaild в сообщении #1545928 писал(а):

(точно - для $2m$ и $2m + 1$ шагов $\frac{C_{2m}^m \cdot (2m + 1)}{2^{2m}} - 1$)

Гениально!
я бы просто написал

$\frac{\sum\limits_{i=1}^{m}2^{2m-2i}\frac{(2i)}{(i!)^{2}}}{2^{2m}}$

А тут такая простая формула!

[ipgmvq]

ipgmvq в сообщении #1546067 писал(а):

я бы просто написал

$\frac{\sum\limits_{i=1}^{m}2^{2m-2i}\frac{(2i)}{(i!)^{2}}}{2^{2m}}$

Опечатка в формуле. Забыл один знак факториала:

$\frac{\sum\limits_{i=1}^{m}2^{2m-2i}\frac{(2i)!}{(i!)^{2}}}{2^{2m}}$

-- 14.01.2022, 15:13 --

sergey zhukov в сообщении #1545958 писал(а):

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

масса вероятности, ибо случайная величина дискретна

И вероятно "самого первого возврата" в ноль?

[sergey zhukov]

ipgmvq
Нет, не самого первого. Это плотность (так привычнее) вероятности возврата в ноль на $N$-ом шаге. Учитываются все возвраты. Сгенерированно множество кривых блуждания и для каждой из них отмечены все ее точки возврата в ноль. Затем результат по всем кривым усреднен.

Самый первый возврат - это предыдущая гистограмма. Она отличается от этой (вероятность того, что на шаге $N$ будет именно первый возврат, падает гораздо быстрее, чем вероятность того, что на шаге $N$ будет один из возвратов). Например, медиана распределения первого возврата равна практически 2 шага. Т.е. вероятность того, что первое достижение нуля произойдет уже на втором шаге такая же, как и вероятность того, что оно произойдет на каком-либо из последующих шагов или не произойдет вообще.

[ipgmvq]

sergey zhukov
А понял, что это за новый график. Однако тогда это просто нормализованный график количества досижения нулевого баланса, и его значения по оридинате сложно считать массой вероятности, ведь то, что мы имеем по оси абсцисс не является независимыми случайными событиями. Например, вероятность достижения нуля на 100-м голосе будет существенно зависить от того, достигался ли ноль на 98 голосе. Мы по сути имеем дело с временным рядом своего рода, подчеркиваю рядом. Возвращаясь к примеру с (дискретной до цента) ценой акции, это как рисовать "плотность/массу вероятности" закрывающей цены акции минутных баров ровно на 105.00, если она стартует в начале сессии ровно с 100.00. Кажду последующую минуту вероятность закрывающей цены 105.00 будет сильно зависеть от того, была ли она 105.00 в конце предыдущей минуты... Мы пытаемся не учитывать вычурную зависимость (автокорреляцию) между интегралами последовательности изначально независимых друг от друга случайных величин.

[ipgmvq]

sergey zhukov
Или по-иному вероятность того, что баланс вернется в ноль одновременно на 100-м голосе и, например, 90-м голосе, не равна сумме масс вероятностей того, что будет возвращение на 100-м голосе и 90-м голосе по отдельности с этого графика.

[sergey zhukov]

ipgmvq
Возможно, это распределение нужно назвать просто средней плотностью точек достижения нуля. Т.е. в каждом отдельном испытании (один из $2^N$ путей) мы получаем в общем случае несколько точек достижения нуля, средняя плотность которых описывается этой кривой.

Т.е. результатами испытания являются все возможные способы распределения множества нулевых точек по оси абцисс. Вероятности этих событий надлежит искать. А эта кривая - матожидание этих событий. Она даже нормирована, похоже, неправильно. Ее нужно было нормировать на число испытанных путей, а не на единичную площадь.

[ipgmvq]

sergey zhukov в сообщении #1546141 писал(а):

средней плотностью точек достижения нуля

Проблема в том, что эти плотности зависят друг от друга.

К примеру, у нас 4 избирателя. И соответственно 16 траекторий. Из них 8 траекторий придут в ноль на голосе 2, и 6 на голосе 4. Но из тех 8, что были на нуле на 2-м голосе, 4 будут на нуле на 4-м голосе, а из 8, которые не были на нуле на 2-м голосе, только 2 будут на нуле на 4-м голосе.
Вероятность того, что траектория вернется в ноль на 2-м голосе составляет $50\%$ (8 траекторий из 16). Вероятность того, что траектория вернется в ноль на 4-м голосе составляет $37,5\%$ (6 траекторий из 16). Вероятность того, что траектория вернется в ноль и на 2-м голосе, и на 4-м составляет не $87,5\%$ (или что там получится после нормализации $37,5\%$, $50,0\%$ и $87,5\%$), но $25\%$ (4 траектории из 16).