Mercury13

Известная теорема теории игр (теорема Нэша).
Любая матричная игра имеет равновесие Нэша в смешанных стратегиях.
А смешанная стратегия — это распределение, с какой вероятностью брать ту или эту стратегию.

Таким образом, распределение Нэша — это та «случайная смесь» стратегий, которая уныла и надёжна, как и полагается равновесию Нэша. Например, для игры «камень-ножницы-бумага» распределение Нэша — все три фигуры по ⅓.

Не совсем так. Главное требование — симметричный шум, иначе оценка будет смещённой.
Но в случае нормального шума МНК превращается в метод максимального правдоподобия. Просто посмотрите на формулу шума, а потом прологарифмируйте.

Коэффициент детерминации тут ни к чему.
Чтобы получить коэффициент детерминации, нужно много статистики и зависимость y(x).
Этот товарищ, насколько я понял, использовал как модель единичный лаг. Взял много команд и футбольных сезонов, модель — сколько очков получено в прошлый год, зависимая переменная — сколько очков в этот год.

R² — это так называемый коэффициент детерминации. Как он работает?
Изначальная дисперсия переменной y будет D1.
Наладили модель — дисперсия модели D2, которая, надо полагать, меньше D1 (особенно если вся выборка обучающая, без экзаменационной; здравствуй, переобучение!).
Тогда R² = 1 − D2/D1 = (D1 − D2) / D1.

Дисперсия, как известно, измеряется в квадратных попугаях. И, кроме того, для независимых величин D(x+y) = Dx+Dy. Таким образом, √(D1 − D2) ~ √R² — это тот разброс, который мы объяснили моделью.

Но он, по-видимому, натягивает сову на глобус. В его модели объяснённый разброс — 0,780 (ещё и округлять не умеет), необъяснённый — √D2 ~ √(1 − R²) = 0,626, и в зависимости от того, что хочешь доказать, можно манипулировать статистикой в ту или иную сторону. Вот так я могу сказать, что с такими разбросами всего на 0,780 / (0,780+0,626) = 55% умение, и на 45% — удача. Так что нет, коэффициент детерминации, и точка. Повторяю, для независимых величин один разброс частично компенсируется другим, и D(x+y) = Dx+Dy. В квадратных попугаях.

Бинарный поиск, однако точка деления — не (a+b)/2, а медиана куска распределения от a до b (т.е. round(F⁻¹([F(a) + F(b)]/2)); F(·) — функция распределения, тупо переделанная из кусочно-постоянного вида в кусочно-линейный, сплайновый или ещё какой-нибудь).
Немного неоптимально, но крайне просто.

З.Ы. Эта штука достаточно оптимальна для «гладких» распределений. В общем случае неоптимальна — например, если у нас три возраста с вероятностями 0,45, 0,1 и 0,45, стоит спросить первый, потом третий и уж при полном невезении второй (среднее 1,65 запроса), а не брать среднее, а затем — первое или второе (в среднем 1,9 запросов).

Если нужен точный оптимум — решать задачу динамического программирования по критерию
N[a,b] = min{c} (1 + (N[a,c−1]p[a,c−1] + N[c+1,b]p[c+1,b]) / p[a,b]).
Граничные условия: при a = b N[a,b] = 1; при a>b N[a,b] = 0.
p[a,b] — суммарная вероятность от a до b включительно; вычисляется как sum[b]−sum[a−1]; sum[i] = sum{x <= i} p(x).
N[0,M] = ?

Или, обозначив Q[a,b] как N[a,b]p[a,b],
Q[a,b] = min{c} (p[c] + Q[a,c−1] + Q[c+1,b]).
Так как p[0,M] = 1, то Q[0,M] = N[0,M].
Граничные условия: при a = b Q[a,b] = p[a]; при a>b Q[a,b] = 0.
Q[0,M] = ?

Решается задача за O(M²) операций. Если нужно хранить всю информацию, чтобы в нужный момент прокрутить цепь запросов — O(M²) памяти; если только указать оптимум — можно обойтись O(M).