У меня возникли проблемы с решением следующего.
Вы берете карты из стандартной колоды из 52 карт без замены, пока не получите туза. Вы вытягиваете из того, что осталось, пока не получите 2. Вы продолжаете с 3. Какое ожидаемое число вы будете иметь после того, как закончится вся колода?
Было естественно позволить
Таким образом, проблема, по сути, состоит в том, чтобы выяснить вероятность того, что вы окажетесь на когда колода закончится, а именно:
Я это вижу
но не мог получить дальше ...
2AAA2
Ответы:
Следуя идее @ Gung, я думаю, что ожидаемое значение будет 5,84? и из моей интерпретации комментариев я предполагаю, что «А» является почти невозможным значением (если только последние четыре карты в колоде не являются тузами). Вот результаты моделирования 10000 итераций Монте-Карло
и вот код R на тот случай, если вы захотите поиграть с ним ..
источник
A
невозможно? Рассмотрим последовательность из 48 карт, а затем,AAAA
например.1/prod( 48:1 / 52:5 )
results
Для симуляции важно быть правильным и быстрым. Обе эти цели предполагают написание кода, предназначенного для основных возможностей среды программирования, а также кода, который является максимально коротким и простым, поскольку простота придает ясность, а ясность способствует правильности. Вот моя попытка достичь обоих в
R
:Применяя этот воспроизводимым способом можно сделать с помощью
replicate
функции после установки случайного начального числа, как и вЭто медленно, но достаточно быстро, чтобы проводить довольно длительные (и, следовательно, точные) симуляции многократно без ожидания. Есть несколько способов показать результат. Давайте начнем с его значения:
Последнее является стандартной ошибкой: мы ожидаем, что смоделированное среднее значение будет в пределах двух или трех SE от истинного значения. Это ставит истинное ожидание где-то между и5,8535.817 5.853 .
Возможно, мы также захотим увидеть таблицу частот (и их стандартных ошибок). Следующий код немного упрощает табуляцию:
Вот вывод:
Как мы можем знать, что симуляция даже правильна? Одним из способов является его тщательное тестирование на небольшие проблемы. По этой причине этот код был написан, чтобы атаковать небольшое обобщение проблемы, заменяя различных карт на и масти на . Однако для тестирования важно иметь возможность кормить код колодой в заранее определенном порядке. Давайте напишем немного другой интерфейс для того же алгоритма:413 4
n
k
(Можно использовать
draw
вместоsim
везде, но дополнительная работа в началеdraw
делает его в два раза медленнееsim
.)Мы можем использовать это, применяя это к каждому отдельному перемешиванию данной колоды. Поскольку целью здесь является лишь несколько разовых тестов, эффективность генерации этих перемешиваний не имеет значения. Вот быстрый способ перебора:
Теперь
d
это фрейм данных, строки которого содержат все тасования. Применитьdraw
к каждой строке и подсчитать результаты:Выход (который мы будем использовать в формальном тесте на мгновение)
( Кстати, значение легко понять: мы все равно будем работать с картой если и только если все двойки предшествуют всем тузам. Вероятность этого (с двумя мастями) равна . Из различных обладают этим свойством.)2 1 / ( 2 + 2420 2 25202520/6=4201/(2+22)=1/6 2520 2520/6=420
Мы можем проверить вывод с помощью критерия хи-квадрат. С этой целью я применяю раз для этого случая различных карт в мастях:10,000 n=4 k=2
sim
п = 4 к = 2Поскольку настолько велико, мы не видим существенной разницы между тем, что говорится, и значениями, вычисленными с помощью исчерпывающего перечисления. Повторение этого упражнения для некоторых других (малых) значений и дает сопоставимые результаты, что дает нам достаточно оснований доверять применительно к и .н кp n k n=13 k=4
sim
sim
к = 4Наконец, тест хи-квадрат с двумя выборками будет сравнивать выходные данные
sim
с результатами, полученными в другом ответе:Огромная статистика хи-квадрат дает p-значение, которое по существу равно нулю: без сомнения,
sim
не согласен с другим ответом. Есть два возможных решения разногласий: один (или оба!) Из этих ответов неверен или они реализуют различные интерпретации вопроса. Например, я интерпретировал «после того, как колода закончилась», чтобы означать после просмотра последней карты и, если это допустимо, обновления «номера, на котором вы будете» перед завершением процедуры. Возможно, этот последний шаг не должен был быть сделан. Возможно, какое-то столь тонкое различие в интерпретации объяснит разногласия, и в этот момент мы сможем изменить вопрос, чтобы сделать его более понятным.источник
Существует точный ответ (в виде матричного произведения, представленного в пункте 4 ниже). Существует достаточно эффективный алгоритм для его вычисления, основанный на следующих наблюдениях:
Случайное перемешивание из карт может быть сгенерировано путем случайного перемешивания карт и затем случайным образом перемежая оставшиеся карт в них.Н КN+k N k
Перетасовывая только тузов, а затем (применяя первое наблюдение) разбрасывая двойки, затем тройки и так далее, эту проблему можно рассматривать как цепочку из тринадцати шагов.
Нам нужно отслеживать больше, чем ценность карты, которую мы ищем. При этом, однако, нам не нужно учитывать положение знака относительно всех карт, а только его положение относительно карт равного или меньшего значения.
Представьте себе метку на первом тузе, а затем отметьте первых двух, найденных после него, и так далее. (Если на каком-либо этапе колода заканчивается без отображения карты, которую мы ищем, мы оставим все карты без отметки.) Пусть «место» каждой отметки (если она существует) будет числом карт равного или меньшего значения, которое были сданы, когда была сделана отметка (включая саму помеченную карточку). Места содержат всю необходимую информацию.
Место после метки является случайным числом. Для данной колоды последовательность этих мест образует стохастический процесс. Фактически это марковский процесс (с переменной матрицей перехода). Таким образом, точный ответ можно рассчитать по двенадцати умножениям матриц.ith
Используя эти идеи, эта машина получает значение (вычисление с плавающей запятой двойной точности) за секунды. Это приближение точного значения является точным для всех отображаемых цифр.1 / 9 19826005792658947850269453319689390235225425695.8325885529019965 1/9
Остальная часть этого поста содержит подробности, представляет рабочую реализацию (в
R
) и завершается некоторыми комментариями по вопросу и эффективности решения.Генерация случайных тасов колоды
На самом деле концептуально яснее и не сложнее математически рассматривать «колоду» (она же мультимножество ) из карт, из которых самого младшего достоинства, следующего младшего и т. Д. , (Заданный вопрос касается колоды, определяемой вектором .)N=k1+k2+⋯+km k1 13 ( 4 , 4 , … , 4 )k2 13 (4,4,…,4)
«Случайное перемешивание» из карт - это одна перестановка, взятая равномерно и случайным образом из перестановок из карт. Эти тасования попадают в группы эквивалентных конфигураций, потому что перестановка «тузов» между собой ничего не меняет, перестановка «двойки» между собой также ничего не меняет и так далее. Поэтому каждая группа перестановок, которые выглядят одинаково, когда масти карт игнорируются, содержитПерестановки. Эти группы, число которых определяется множителемN ! = N × ( N - 1 ) × ⋯ × 2 × 1 N k 1 k 2 k 1 ! × k 2 ! × ⋯ × k м !N N!=N×(N−1)×⋯×2×1 N k1 k2 k1!×k2!×⋯×km!
называются «комбинации» колоды.
Есть еще один способ подсчета комбинаций. Первые карты могут образовывать только комбинация. Они оставляют «слоты» между ними и вокруг них, в которые могут быть помещены следующие карты. Мы могли бы указать это на диаграмме, где " " обозначает одну из карт а " " обозначает слот, который может содержать от до дополнительных карт:k1 k1!/k1!=1 k1+1 k2 ∗ k1 _ 0 k2
Когда дополнительные карты чередуются, шаблон звезд и новые карты карты на два подмножества. Число различных таких подмножеств: .k2 k1+k2 (k1+k2k1,k2)=(k1+k2)!k1!k2!
Повторяя эту процедуру с «тройки», мы обнаруживаем, что есть способы перемежать их среди первых карт. Поэтому общее количество различных способов упорядочить первые таким образом равноk3 ((k1+k2)+k3k1+k2,k3)=(k1+k2+k3)!(k1+k2)!k3! k1+k2 k1+k2+k3
После завершения последних карт и продолжения умножения этих телескопических дробей мы находим, что количество полученных различных комбинаций равно общему количеству комбинаций, как было подсчитано ранее, . Поэтому мы не заметили никаких комбинаций. Это означает, что этот последовательный процесс перетасовки карт правильно фиксирует вероятности каждой комбинации, предполагая, что на каждом этапе каждый возможный особый способ разделения новых карт среди старых выбирается с одинаково равной вероятностью.kn (Nk1,k2,…,km)
Процесс места
Первоначально есть тузов и, очевидно, отмечен самый первый. На более поздних стадиях есть карт, место (если существует отмеченная карта) равно (некоторое значение от до ), и мы собираемся перемежать карты вокруг них. Мы можем визуализировать это с помощью диаграммы, какk1 n=k1+k2+⋯+kj−1 p 1 n k=kj
где " " обозначает отмеченный символ. Условно по этому значению места мы хотим найти вероятность того, что следующее место будет равно (какое-то значение от до ; по правилам игры следующее место должно идти после , откуда ). Если мы сможем найти, сколько существует способов перебросить новых карт в пробелах так, чтобы следующее место равнялось , то мы можем разделить на общее количество способов перемежать эти карты (равное , как мы видели), чтобы получить⊙ p q 1 n+k p q≥p+1 k q (n+kk) вероятность перехода, что место меняется с на . (Также будет вероятность перехода к тому, что место полностью исчезнет, когда ни одна из новых карт не будет следовать за отмеченной картой, но нет необходимости вычислять это явно.)p q
Давайте обновим диаграмму, чтобы отразить эту ситуацию:
Вертикальная полоса « » показывает , где происходит первое новой карты после отмеченной карты: не новые карты не могут , следовательно , появляется между и (и , следовательно , нет слота не показаны на этом интервале). Мы не знаем, сколько звезд в этом интервале, поэтому я только что назвал его (который может быть нулем). Неизвестные исчезнут, как только мы найдем связь между ним и .| ⊙ | s s q
Предположим, что затем мы разбрасываем новых карт вокруг звезд до а затем - независимо от этого - мы чередуем оставшиеся новые карты вокруг звезд после . Естьj ⊙ k−j−1 |
способы сделать это. Обратите внимание, что - это самая сложная часть анализа - что место равно потому что| p+s+j+1
Таким образом, дает нам информацию о переходе от места к месту . Когда мы тщательно отслеживаем эту информацию для всех возможных значений и суммируем все эти (непересекающиеся) возможности, мы получаем условную вероятность места после места ,τn,k(s,p) p q=p+s+j+1 s q p
где сумма начинается в и заканчивается в . (Переменная длина этой суммы предполагает, что есть вряд ли это будет замкнутая формула для него как функция от и , за исключением особых случаев.)j=max(0,q−(n+1)) j=min(k−1,q−(p+1) n,k,q, p
Алгоритм
Первоначально существует вероятность что место будет а вероятность будет иметь любое другое возможное значение в . Это может быть представлено вектором .1 1 0 2,3,…,k1 p1=(1,0,…,0)
После разбрасывания следующих карт вектор обновляется до путем умножения его (слева) на матрицу перехода . Это повторяется до тех пор, пока не будут размещены все карты . На каждом этапе сумма записей в векторе вероятности - это вероятность того, что какая-либо карта была помечена. То, что осталось сделать значение равным - это вероятность того, что после шага не останется ни одной карты.k2 p1 p2 (Prk1,k2(q|p),1≤p≤k1,1≤q≤k2) k1+k2+⋯+km j pj 1 j , Таким образом, последовательные различия в этих значениях дают нам вероятность того, что мы не смогли найти карту типа для отметки: это распределение вероятностей значения карты, которую мы искали, когда колода заканчивается в конце игры. ,j
Реализация
Следующий(n+kk)
R
код реализует алгоритм. Это параллельно предыдущему обсуждению. Во-первых, вычисление вероятностей перехода выполняетсяt.matrix
(без нормализации с делением на , что облегчает отслеживание вычислений при тестировании кода):Это используетсяpj−1 pj p1
transition
для обновления до . Он рассчитывает матрицу переходов и выполняет умножение. Это также заботится о вычислении начального вектора если аргумент является пустым вектором:p
Теперь мы можем легко вычислить вероятности немаркировки на каждом этапе для любой колоды:
Вот они для стандартной колоды:
Выход
Согласно правилам, если король был помечен, то мы не будем искать другие карты: это означает, что значение должно быть увеличено до . При этом различия дают распределение «числа, на котором вы будете, когда закончится колода»:0.9994461 1
(Сравните это с результатом, о котором я сообщаю в отдельном ответе, описывающем моделирование по методу Монте-Карло: они кажутся одинаковыми, вплоть до ожидаемого количества случайных изменений.)
Ожидаемое значение является немедленным:
В общем, для этого требовалось всего около десятка строк исполняемого кода. Я проверил это с помощью ручных расчетов для малых значений (до ). Таким образом, если какое-либо несоответствие становится очевидным между кодом и предшествующим анализом проблемы, доверяйте коду (потому что анализ может иметь опечатки).k 3
замечания
Отношения с другими последовательностями
Когда есть одна из каждой карты, распределение представляет собой последовательность обратных целых чисел:
Значение на месте это(начиная с места ). Это последовательность A001048 в онлайн-энциклопедии целочисленных последовательностей. Соответственно, мы могли бы надеяться на закрытую формулу для колод с константой («подходящих» колод), которая обобщала бы эту последовательность, которая сама по себе имеет некоторые глубокие значения. (Например, он подсчитывает размеры наибольших классов сопряженности в группах перестановок и также связан с триномиальными коэффициентами .) (К сожалению, обратные значения в обобщении для обычно не являются целыми числами.)i i!+(i−1)! i=1 ki k>1
Игра как случайный процесс
Наш анализ показывает, что начальные коэффициенты векторов , , являются постоянными. Например, давайте отследим вывод, как он обрабатывает каждую группу карт:i pj j≥i
game
...
Например, второе значение окончательного вектора (описывающее результаты с полной колодой из 52 карт) уже появилось после обработки второй группы (и равно ). Таким образом, если вы хотите получить информацию только о разметке через значение карты , вам нужно выполнить расчет только для колоды из карт.1/(84)=1/70 jth k1+k2+⋯+kj
Поскольку вероятность не пометить карту со значением быстро приближается к при увеличении , после типов карт в четырех мастях мы почти достигли предельного значения для ожидания. Действительно, предельное значение составляет приблизительно (рассчитано для колоды из карт, в которой ошибка округления двойной точности не позволяет двигаться дальше).j 1 j 13 5.833355 4×32
тайминг
Глядя на алгоритм, примененный к вектору , мы видим, что его время должно быть пропорционально и - используя грубую верхнюю границу - не хуже, чем пропорционально . По синхронизации все вычисления для через и через , и анализируя только те , кто принимает относительно длительного времени ( секунды или дольше), я оценить время вычисления приблизительно , поддерживая эту оценку сверху.( к , к , ... , K ) K 2 м 3 K = 1 7 п = 10 30 1 / 2 O ( K 2 н 2.9 )m (k,k,…,k) k2 m3 k=1 7 n=10 30 1/2 O(k2n2.9)
Одним из применений этих асимптотик является прогнозирование времени расчета для более крупных задач. Например, учитывая, что случай занимает около секунды, мы оценили бы, что (очень интересный) случай займет около секунды. (На самом деле это занимает секунды.)1,31 к = 1 , п = 100 1,31 ( 1 / 4 ) 2 ( 100 / 30 ) 2,9 ≈ 2,7 2,87k=4,n=30 1.31 k=1,n=100 1.31(1/4)2(100/30)2.9≈2.7 2.87
источник
Взломал простой Монте-Карло в Perl и нашел примерно .5.8329
источник