Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 81
>Мат ожидание: Mx = 255.054;
— А считать медиану и моду не пробовали? А то ведь средняя зарплата в деревне Трофимово — ~100 000 тысяч рублей, при том, что 99 человек получают по 1 000 в месяц, а один (бизнесмен, допустим занимается лесом, и на него все пашут) — 10 000 000. Вообще, в реальном мире приоритет оценки параметров средними значениями такой (от большего к меньшему):
медиана -> мода -> математическое ожидание.
Есть ложь, есть большая ложь и есть статистика. (с) Марк Твен
— А считать медиану и моду не пробовали? А то ведь средняя зарплата в деревне Трофимово — ~100 000 тысяч рублей, при том, что 99 человек получают по 1 000 в месяц, а один (бизнесмен, допустим занимается лесом, и на него все пашут) — 10 000 000. Вообще, в реальном мире приоритет оценки параметров средними значениями такой (от большего к меньшему):
медиана -> мода -> математическое ожидание.
Есть ложь, есть большая ложь и есть статистика. (с) Марк Твен
> А считать медиану и моду не пробовали?
Не пробовал, был уверен, что функции распределения достаточно, для того чтобы увидеть полную картину.
Не пробовал, был уверен, что функции распределения достаточно, для того чтобы увидеть полную картину.
>А судя по дисперсии, если беретесь играть в эту игру — даже не думайте на что-то рассчитывать)
— А это чьи слова? Вот посчитаете медиану, тогда можно говорить, о каком-то расчете. Я вообще нисколько не принижаю роль функции распределения, просто если уж начинаете оценивать средний результат, то делайте это по науке, рассмотрите все варианты.
А полная картина кстати чем-то напоминает одну ветку колокола распределения Гаусса :-)
Ну вид явно какой-то экспоненциально убывающий.
— А это чьи слова? Вот посчитаете медиану, тогда можно говорить, о каком-то расчете. Я вообще нисколько не принижаю роль функции распределения, просто если уж начинаете оценивать средний результат, то делайте это по науке, рассмотрите все варианты.
А полная картина кстати чем-то напоминает одну ветку колокола распределения Гаусса :-)
Ну вид явно какой-то экспоненциально убывающий.
Очень вряд ли эта функция убывает экспоненциально. Потому что, если так, то дисперсия не была бы такой большой. А здесь её скорее всего вообще не существует.
Впрочем и посчитать ничего не стоит:
Медиана = 90.
Мода = 25.
И все-же мат. ожидание, я думаю, более релевантное понятие в данном контексте.
Медиана = 90.
Мода = 25.
И все-же мат. ожидание, я думаю, более релевантное понятие в данном контексте.
Виноват, прочитал подробней, действительно лучше медианой оценивать.
Во-первых, теоретически, тут нужно подбирать функцию, которая близко аппроксимирует ряд значений случайных величин, ну там с некоторым небольшим отклонением. Иначе вы посчитаете только значения на определенной выборке(то есть не идеальное мат. ожидание, а просто среднее и так далее).
Во-вторых, вы как считали медиану? Отсортировали по числу ходов все 1 000 000 симуляций и взяли 500 000-й элемент? Если так, то я вам верю. Если нет, давайте код, посмотрим.
Во-третьих, вы используете random(), который скорее всего даёт равномерное распределение, но никак не доказываете, что случайность в игре имеет именно такой характер, это еще тоже тонкий момент, который стоило рассмотреть в самом начале рассуждений.
Во-вторых, вы как считали медиану? Отсортировали по числу ходов все 1 000 000 симуляций и взяли 500 000-й элемент? Если так, то я вам верю. Если нет, давайте код, посмотрим.
Во-третьих, вы используете random(), который скорее всего даёт равномерное распределение, но никак не доказываете, что случайность в игре имеет именно такой характер, это еще тоже тонкий момент, который стоило рассмотреть в самом начале рассуждений.
> то есть не идеальное мат. ожидание, а просто среднее и так далее
Знаю, изначально хотел послать статью в хаброюмор, но получилось только в песочницу.
Код подсчета медианы. a — массив результатов испытаний.
QList* pp = new QList();
for (int i = 0; i < cc; i++)
pp->append(a[i]);
qSort(*pp);
qDebug() << (pp->at(cc / 2) + pp->at(cc / 2 — 1)) / 2;
По поводу random — согласен, хотя и то, что там на выходе равномерное распределение — совсем не очевидно, даже думать боюсь об этом :).
Знаю, изначально хотел послать статью в хаброюмор, но получилось только в песочницу.
Код подсчета медианы. a — массив результатов испытаний.
QList* pp = new QList();
for (int i = 0; i < cc; i++)
pp->append(a[i]);
qSort(*pp);
qDebug() << (pp->at(cc / 2) + pp->at(cc / 2 — 1)) / 2;
По поводу random — согласен, хотя и то, что там на выходе равномерное распределение — совсем не очевидно, даже думать боюсь об этом :).
Описанный Вами случай называется «средняя температура по больнице 36.6 (включая морг)»
Может и можно, но я не имею представления как это сделать.
Можно построить грубую непрерывную модель. Пусть в каждом раунде k генератор выдает игрокам две реализации r_k1 и r_k2 равномерно распределенной (для удобства — от 0 до 1) случайной величины, а результатом k-го раунда служит s_k = sign(r_k1 — r_k2). Тогда вероятность завершить игру не более, чем за n ходов, грубо говоря, есть P_n := Pr( abs(s_1 +… + s_n) >= 9 ) для колоды из 36 карт.
Несложно видеть, что s_k равна 1 или -1 с вероятностями 1/2. Ее мат. ожидание равно 0, а дисперсия — 1. Тогда по центральной предельной теореме распределение s_1 +… + s_n близко к N(0, n). Отсюда P_n = 1 — erf( 9 / sqrt(2n) ).
Например, P_n(178) ~ 0,5, т. е. в непрерывном случае медиана длительности игры — 178 ходов.
Я давно не вспоминал теорвер, так что если где наврал — проше прощения.
Эта модель не учитывает а) дискретности номинала карт, б) неслучайности перераспределения карт после победы в раунде. Интересно, что из этого фатальнее для результата.
TheHorse, можно попросить вас промоделировать игру, если брать номинал карт не дискретным 0, 1, 2… 8, а непрерывным? Интересно, какие результаты получатся.
Несложно видеть, что s_k равна 1 или -1 с вероятностями 1/2. Ее мат. ожидание равно 0, а дисперсия — 1. Тогда по центральной предельной теореме распределение s_1 +… + s_n близко к N(0, n). Отсюда P_n = 1 — erf( 9 / sqrt(2n) ).
Например, P_n(178) ~ 0,5, т. е. в непрерывном случае медиана длительности игры — 178 ходов.
Я давно не вспоминал теорвер, так что если где наврал — проше прощения.
Эта модель не учитывает а) дискретности номинала карт, б) неслучайности перераспределения карт после победы в раунде. Интересно, что из этого фатальнее для результата.
TheHorse, можно попросить вас промоделировать игру, если брать номинал карт не дискретным 0, 1, 2… 8, а непрерывным? Интересно, какие результаты получатся.
Фатальней б) — проверено.
Для новой модели:
Карты — случайные значения 0..1?
Для новой модели:
Карты — случайные значения 0..1?
О, а я-то наврал. На самом деле, обозначив S_n = abs(s_1 +… + s_n), имеем P_n = Pr(S_1 >= 18 или… или S_n >= 18) = Pr( (S_1 >= 18) или (S_1 ) ). Надо подумать, как бы поудобнее вычислить такую вероятность.
Буквально вчера слушал доклад на эту тему на одной математической конференции, вот здесь лежат тезисы. Оказывается, довольно непростой сюжет…
по-хорошему нужно нагрузить кластер на вычисление всех результатов :)
всегда вариантов-то 36! / (4! * 9) ~ 2e39
всегда вариантов-то 36! / (4! * 9) ~ 2e39
Вариантов 36! / 18! (и это если масти учитывать) ~ 5e25. 36! / 18! — количество вариантов вытягивания 18 карт из колоды (полностью задает раздачу карт).
И это прокатит если раздача карт имеет равномерное распределение, что очень не тривиально доказать и нужен кластер чтобы проверить).
И это прокатит если раздача карт имеет равномерное распределение, что очень не тривиально доказать и нужен кластер чтобы проверить).
Во-первых, 36! / (4! ^ 9) ~ 1.4e29. Во-вторых, это только число вариантов для начального расклада, а там дальше ещё вносится случайность «Важно чтобы карты со стола… при этом также перетасовывались (чтобы исключить возможность циклов)», так что перебор существенно больше. Между прочим, похоже, что возможна сколь угодно длинная партия — если всё время будет случаться неудачная перетасовка — но вероятность партии длины >=N экспоненциально убывает по N — если удачные перестановки вообще существуют, — так что матожидание числа ходов конечно.
да, зачем-то умножил а не возвёл в степень.
Да, могут быть случаи с зашкаливающим количеством ходов. Для этого я в коде написал:
if (counter > 100000) player1->clear();
— то есть, если игра идет около недели, то первый игрок просто покидает игру.
P. S. по поводу комбинаторики, вы абсолютно правы, я не учел порядок.
if (counter > 100000) player1->clear();
— то есть, если игра идет около недели, то первый игрок просто покидает игру.
P. S. по поводу комбинаторики, вы абсолютно правы, я не учел порядок.
Откуда взяли, что вероятность партии длины >= N экспоненциально убывает по N?
Есть довольно общее рассуждение.
Число состояний игры заведомо конечно, пусть оно n. Из каждого состояния с какими-то вероятностями можно завершить игру и перейти в другие состояния. Вероятности перехода сведём в матрицу M размера n*n. Рассмотрим для каждого N вектор из n чисел, i-е из которых есть вероятность того, что игра за N ходов не закончилась и находится в состоянии i. Делаем очередной ход, пусть игра не закончилась. Вероятность оказаться после этого хода в фиксированном состоянии рассчитывается по формуле полной вероятности как сумма произведений. На языке матриц это соответствует умножению вектора на M. Таким образом, после N шагов рассматриваемый вектор есть просто N-я степень матрицы M, умноженная на начальное состояние.
Рассмотрим матрицу, транспонированную к M. Сумма в i-й строке в этой матрице есть вероятность перехода из состояния i куда-нибудь; это заведомо число от 0 до 1, причём строго меньшее 1, если из состояния можно закончить игру. Легко видеть, что собственные значения у такой матрицы обязаны быть по модулю нестрого меньше единицы, причём собственное значение, равное по модулю единице, возможно только в случае наличия группы состояний, из которой нет выхода. При наличии оговорки «если удачные перестановки вообще существуют» — которая представляется выполненной — все собственные значения матрицы, транспонированной к M, по модулю строго меньше 1. Соответственно, собственные значения M тоже по модулю строго меньше 1.
Меняя базис, приводим M к нормальной форме; тогда на главной диагонали стоят числа, по модулю меньшие единицы. Возможно, на единицу вправо есть ещё что-то ненулевое, но оно не оказывает влияния на происходящее. Все остальные элементы равны нулю. При возведении в степень N все элементы матрицы экспоненциально убывают по N, так что и итоговый вектор, будучи их фиксированной линейной комбинацией, тоже экспоненциально убывает по N.
Число состояний игры заведомо конечно, пусть оно n. Из каждого состояния с какими-то вероятностями можно завершить игру и перейти в другие состояния. Вероятности перехода сведём в матрицу M размера n*n. Рассмотрим для каждого N вектор из n чисел, i-е из которых есть вероятность того, что игра за N ходов не закончилась и находится в состоянии i. Делаем очередной ход, пусть игра не закончилась. Вероятность оказаться после этого хода в фиксированном состоянии рассчитывается по формуле полной вероятности как сумма произведений. На языке матриц это соответствует умножению вектора на M. Таким образом, после N шагов рассматриваемый вектор есть просто N-я степень матрицы M, умноженная на начальное состояние.
Рассмотрим матрицу, транспонированную к M. Сумма в i-й строке в этой матрице есть вероятность перехода из состояния i куда-нибудь; это заведомо число от 0 до 1, причём строго меньшее 1, если из состояния можно закончить игру. Легко видеть, что собственные значения у такой матрицы обязаны быть по модулю нестрого меньше единицы, причём собственное значение, равное по модулю единице, возможно только в случае наличия группы состояний, из которой нет выхода. При наличии оговорки «если удачные перестановки вообще существуют» — которая представляется выполненной — все собственные значения матрицы, транспонированной к M, по модулю строго меньше 1. Соответственно, собственные значения M тоже по модулю строго меньше 1.
Меняя базис, приводим M к нормальной форме; тогда на главной диагонали стоят числа, по модулю меньшие единицы. Возможно, на единицу вправо есть ещё что-то ненулевое, но оно не оказывает влияния на происходящее. Все остальные элементы равны нулю. При возведении в степень N все элементы матрицы экспоненциально убывают по N, так что и итоговый вектор, будучи их фиксированной линейной комбинацией, тоже экспоненциально убывает по N.
Единственное, чего не смог понять: почему все элементы матрицы экспоненциально убывают по N?
Ячейка жордановой нормальной формы из одного числа (x) после возведения в степень N становится равной (x^N); поскольку |x|<1, то это экспоненциальное убывание. Ячейка 2*2, то есть (x 1 // 0 x), после возведения в степень N становится равной (x^N Nx^{N-1} // 0 x^N), то есть опять же экспоненциальное убывание. Для больших размеров аналогично — когда матрица фиксирована, при возведении в растущую степень появляются вещи типа C N^k x^N, где C, k, x фиксированы и |x|<1, и при больших N это даёт экспоненциальное убывание.
В общем случае жордановых ячеек много, но они ведут себя независимо, давая в результате что-нибудь типа (x1^N 0 0 0 // 0 x2^N Nx2^{N-1} 0 // 0 0 x2^N 0 // 0 0 0 x3^N).
Замена базиса при приведении к нормальной форме просто перетасовывает эти убывающие элементы с фиксированными коэффициентами.
В общем случае жордановых ячеек много, но они ведут себя независимо, давая в результате что-нибудь типа (x1^N 0 0 0 // 0 x2^N Nx2^{N-1} 0 // 0 0 x2^N 0 // 0 0 0 x3^N).
Замена базиса при приведении к нормальной форме просто перетасовывает эти убывающие элементы с фиксированными коэффициентами.
Рассмотрим какую-нибудь игру с конечным числом состояний, и которую можно описать марковской цепью. Получается, что для любой такой игры вероятность закончить её за n ходов экспоненциально убывает по n?
Вероятность не закончить её за n ходов.
Либо да, либо существует ненулевая вероятность бесконечно долгой игры.
Либо да, либо существует ненулевая вероятность бесконечно долгой игры.
Плюс ещё время должно быть однородным. Обычно это подразумевается, но лучше уточнить. Если вероятности переходов зависят от номера шага, то легко построить контрпример, где вероятность остаться в игре убывает как угодно.
как у вас игра может закончиться за 10 ходов если сдают по 18 карт? при шаге в 5 первые три столбца должны быть 0 (18 карт сдают, значит минимум 18 ходов).
Если вы ситуацию спора считаете за один ход то да, может и за один ход игра кончиться, но это как-то дико малая вероятность, а у вас пик на столбце 5-10 уже прилично игр заканчивается. Где-то помоему что-то нетак
Если вы ситуацию спора считаете за один ход то да, может и за один ход игра кончиться, но это как-то дико малая вероятность, а у вас пик на столбце 5-10 уже прилично игр заканчивается. Где-то помоему что-то нетак
Одним ходом называю набор действий который приводит к тому, что одна из сторон забирает карты со стола.
Стоило подписать ось Y.
И у Вас изображена не «функция распределения случайной величины», а плотность распределения вероятностей случайной величины.
И у Вас изображена не «функция распределения случайной величины», а плотность распределения вероятностей случайной величины.
Случайную перестановку лучше генерировать «по Кнуту», второй том. Онлайн, например, здесь: http://neerc.ifmo.ru/mediawiki/index.php/Метод_генерации_случайной_перестановки,_алгоритм_Фишера-Йетса. При вашем подходе не будет равновероятности всех перестановок — хотя бы потому, что 36^(2*1000) не делится на 36!..
График очень напоминает как гамма-функцию, так и лог-нормальное распределение.
Сделайте, пожалуйста для меня гистограмму не f, а LN(f)?
Сделайте, пожалуйста для меня гистограмму не f, а LN(f)?
А я считаю, что правильным параметром будет именно матожидание, а не медиана. Единственная тонкость — из рассмотрения надо выбрасывать циклические варианты, которые вызывают бесконечную игру, либо останавливать их после начала повтора.
Рассмотрение матожидания более логично: если мы сыграем 100 партий, то наше время будет приближенно именно к матожиданию. В случае с людьми получающими 1000 и 10000000 рублей мы хотим получить некоторую характеристику сообщества не имеющую отношение к статистике, а имеющую эмпирическую подоплёку. Это скорее уже социология. Хотя не спорю, что в алгоритмах, обрабатывающих сырые данные при и медиану и математическое ожидание и моду я использую одинаково часто. Но для разных целей.
Кстати, интересный момент. Распределение очень напоминает Пуассоновское. Более того, у меня есть подозрение, что хвост распределения будет куда лучше аппроксимироваться Пуассоном, чем Гауссом… У Пуассона затухание не экспоненциальное.
Рассмотрение матожидания более логично: если мы сыграем 100 партий, то наше время будет приближенно именно к матожиданию. В случае с людьми получающими 1000 и 10000000 рублей мы хотим получить некоторую характеристику сообщества не имеющую отношение к статистике, а имеющую эмпирическую подоплёку. Это скорее уже социология. Хотя не спорю, что в алгоритмах, обрабатывающих сырые данные при и медиану и математическое ожидание и моду я использую одинаково часто. Но для разных целей.
Кстати, интересный момент. Распределение очень напоминает Пуассоновское. Более того, у меня есть подозрение, что хвост распределения будет куда лучше аппроксимироваться Пуассоном, чем Гауссом… У Пуассона затухание не экспоненциальное.
Ну и что что влияет хвост? Вероятность попасть в этот хвост никто не отменял. А если мы в него попадаем — игра будет длиться очень долго, что компенсирует вероятность быстрой игры.
Извиняюсь, не в тот трэд ткнул ответить.
Хвост такой, что попадание в него оставит игру незаконченной.
Но ведь мы сыграем эту игру и потеряем на неё соответствующее время?
Да, но это время будет меньшим, чем если бы доигрывали каждую игру до конца.
в матстатистике обычно рассчитывают
величину промежутка, которая превышает 0.707 ( 1 / корень из 2х) функции распределения.
величину промежутка, которая превышает 0.707 ( 1 / корень из 2х) функции распределения.
Не хочу показаться занудой, но что это за тег такой «теория вероятности»? Такой дисциплины не существует (как и «теория множества», или «сопротивление материала»). На мой взгляд, это сильно портит впечатление.
Общие замечания — методика (количество экспериментов, код генерации) взяты уж слишком вольно. Где доверительный интервал, оценка характеристик входного шума?
Как известно, «мелочи не прощают пренебрежительного отношения к себе и мстят по крупному».
Но, в принципе, попытка опереться на ЗБЧ радует (многие совсем забывают, что имеют под рукой потрясающее средство для моделирования подобных событий).
Общие замечания — методика (количество экспериментов, код генерации) взяты уж слишком вольно. Где доверительный интервал, оценка характеристик входного шума?
Как известно, «мелочи не прощают пренебрежительного отношения к себе и мстят по крупному».
Но, в принципе, попытка опереться на ЗБЧ радует (многие совсем забывают, что имеют под рукой потрясающее средство для моделирования подобных событий).
У вас ошибка:
if ((p1 > p2) || ((p1 == 0) && (p2 == 8))). При p1 = 8 и p2 = 0, неправильный ответ.Вы можете расшарить код где то? Мода равная 25 очень подозрительная.
Мода, несмотря на все допущенные ошибки, нормальная и равна 25.
Печально то, что обнаружил еще одну ошибку правка которой полностью убирает хвост.
Код: quaternion.info/zzz.zip
Печально то, что обнаружил еще одну ошибку правка которой полностью убирает хвост.
Код: quaternion.info/zzz.zip
У вас ошибка:
Даже когда p1 = -1, цикл выполняется дважды. Для того чтобы быть уверенным что у вас все правильно просимулируйте дебагом одну игру и проследите за ней. Я уверен что у вас ошибка и мода не должна быть равна 25!
for (int i = 0; i < 1 + (p1 >= 0); i++)
if (player1->count() > 0) {
p1 = player1->first();
temp->append(p1);
player1->removeFirst();
}Даже когда p1 = -1, цикл выполняется дважды. Для того чтобы быть уверенным что у вас все правильно просимулируйте дебагом одну игру и проследите за ней. Я уверен что у вас ошибка и мода не должна быть равна 25!
на Пуассона похоже. Его я «на глазок» и ожидал.
хорошее исследование, только никаких выводов не сделано.
что все эти цифры и графики означают применительно к самой игре «пьяница»?
есть ли расхождения с реальными опытами? отличия результатов с компьютерной игрой?
что все эти цифры и графики означают применительно к самой игре «пьяница»?
есть ли расхождения с реальными опытами? отличия результатов с компьютерной игрой?
Правильный алгоритм генерации случайной перестановки:
Можно доказать, что если rng(a, b) возвращает случайное число с равномерным распределением в [a, b], то вероятность каждой из перестановок — 1/n!..
int gen(int* a, int n)
{
a[0] = 1;
for (int i = 1; i < n; ++i)
{
a[i] = i + 1;
swap(a[i], rng(0, i - 1));
}
}Можно доказать, что если rng(a, b) возвращает случайное число с равномерным распределением в [a, b], то вероятность каждой из перестановок — 1/n!..
QList* temp = new QList();Ааааа он же неявно разделяемый! Зачем такое надо? Выделяйте на стеке списки и не парьтесь.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Распределение количества ходов в карточной игре 'Пьяница'