Задача на комбинаторику

[green_fr]

У Анюты на экзамене была задача. Есть колода 52 карты. Мы тянем карты одну за другой (без возврата карт в колоду) до тех пор, пока не попадём на туза. Наша случайная переменная — порядковый номер первого туза в колоде. Какое мат. ожидание у этой переменной?

Интуитивно задача решается достаточно просто. Если у нас в колоде один туз, он в среднем как бы делит колоду на две части, правильный ответ n/2, где n — количество карт в колоде. Если у нас 2 туза, то они делят колоду на 3 части, ответ n/3. И так далее, значит правильный ответ с 4 тузами 52/5=10,4.

В принципе, это даже можно вывести формулами, через приближение суммы интегралом. По крайней мере на двух тузах это делается: каждая раздача с двумя тузами соответствует клеточке (X, Y), где X — положение первого туза, Y — положение второго. Все раздачи равновероятны, но нас интересует положение первого туза. Переформулируем: нас интересует среднее X, но только такое, где X < Y — то есть, интеграл не по квадрату, а по треугольнику. Когда мы интегрируем, у нас получается x^2dx, в процессе интегрирования которого вылезает та самая 1/3, которая в правильном ответе. Можно, наверное, довести до ума эту формулу и с 4 тузами. Но, во-первых, это явно не то решение, на которое рассчитывает лектор. И по-любому, это же приближение: у нас изначально была сумма, а не интеграл. Как решать эту задачу «честно»?

Мат. ожидание дискретной переменной — это сумма по всем значениям k*P(x=k). Я даже могу выписать P(x=k), но там получается достаточно уродская дробь с 4 факториалами, и я не вижу, как можно упростить / посчитать эту сумму.

Спросил, понятное дело, у ChatGPT. Сначала по-русски. Тот начал с геометрического распределения, ответ 13. Нет, говорю, это если мы каждую карту на место кладём и снова перемешиваем. А, говорит, точно! Значит ответ 53/5=10,6. В принципе, совместимо с тем, что я написал — действительно, в случае с одним тузом у нас не n/2, а (n+1)/2. Но как он это посчитал? Он ссылается на формулу как на «известный факт». Просишь вывести «известный факт» — он его выводит, заменяя самую интересную часть на «можно показать (по свойствам порядковых статистик)». Просишь разжевать это — пишет примерно то же самое, но с «после некоторых алгебраических преобразований». И только после того, как просишь его и это разжевать — что-то пишет, из чего можно восстановить доказательство. Долгое и нудное, но правильное. В частности подсмотрел у ChatGT другую формулу для мат. ожидания: сумма P(x>=k). Работает только, когда возможные значения — последовательные целые числа, но у нас именно этот случай, и в этой форме результат записывается проще.

Спросил то же самое по-французски. ChatGPT сразу написал какую-то галиматью с выводом кучи совершенно ненужных вещей, а последней фразой сказал, что нужно разделить всё на количество тузов, и вместо того, чтобы разделить свою галиматью на 4, разделил непонятно откуда взявшееся 53 на 5, чтобы получить правильный ответ. В этот момент я попытался представить работу современного преподавателя, которому нужно вот это проверять :-)

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

Собственно, вопрос: а как это решать в условиях экзамена? Предположим, мы не помним правильного ответа, и наша интуиция временно отошла, надо именно вывести формулу. Это реально сделать за несколько минут? Экзамен на 2 часа, в нём 30 вопросов.

Comments

[juan_gandhi]

Прежде всего, надо забыть, что мы выбираем в каком-то порядке. n карт. Вероятность вытянуть с k-й попытки 1/n (так?). Ну и суммируем, получаем (n+1)/2. Это в предположении равномерного распределения.

[green_fr]

С одним тузом так. А с двумя? А с четырьмя?

[juan_gandhi]

Какова вероятность попасть на одного туза из m среди n карт? m/n (при прочих равных).
Среднее будет

m/n + 2*(n-1/n)*m/(n-1) +... + (n-m)/(n-m+1)/n*m/(n-m+1) + (n-m)*(n-m)/n =
m/n + 2*m/n+...+(n-m)*m/n =
(((n-m+1)*(n-m+2)/2 - (m-1)*m/2)/n.

Конечно, это прикидка с ходу, я б проверил ещё на (3,2): 1/3 + 2*2/3 = 5/3

[green_fr]

Эту логику я уже не понимаю. Ну и ответ она даёт неправильный. Я на всякий случай проверил (Excel, Monte Carlo), ответ таки 10,6. То есть (n+1)/(m+1).

[juan_gandhi]

Oh shit. Я сильно ошибся, конечно. Формула получается хитрая.

Optional stopping theorem

[alexey_ivanov]

Это решается при помощи использовании понятия stopping time

https://math.stackexchange.com/questions/4751950/expected-number-of-cards-to-draw-before-first-ace-using-stopping-times

[green_fr]

Если я правильно понял термин, то да, формула суммы с произведением - это и есть то, что я назвал "уродской дробью с 4 факториалами". Если есть Excel и нет необходимости выводить формулу, то этого вполне может быть достаточно.

[sobriquet9]

Ожидаемое количество карт до туза 48/5=9.6, потому что не-тузов в колоде 52-4=48 и каждая из них может оказаться перед всеми тузами с вероятностью 1/5. Порядковый номер туза тоже 9.6, если считать начинаем с единицы.

[green_fr]

Да, именно так. Только последняя фраза "если считать начинаем с нуля". Иначе порядковый номер туза 10,6.

[turgutmakbak]

Допустим, у нас есть n карт в колоде, m из них «хорошие», а остальные — «плохие». Сколько есть вариантов того, что первая хорошая карта — r-тая сверху? Понятно, что верхние r-1 карт — плохие, карта номер r — хорошая, а остальные m-1 хороших карт находятся среди нижних n-r карт. Таким образом, количество вариантов, при которых первая сверху хорошая карта — r-тая сверху в колоде, равно C(n-r,m-1). Значит, мат. ожидание положения верхней хорошей карты в колоде равно сумме r*C(n-r,m-1)/C(n,m) по r от 1 до n.

Рассмотрим только числитель, сумму r*C(n-r,m-1) по r от 1 до n. Слагаемое в этой сумме можно записать как C(r,1)*C(n-r,m-1). Представим себе его по другому: допустим, у нас есть n+1 карта, из них m+1 «хороших», и мы считаем количество возможных колод, в которых вторая сверху хорошая карта — (r+1)-ая сверху в колоде. Таких колод тоже C(r,1)*C(n-r,m-1). Суммируя по r от 1 до n, мы получаем просто количество всех колод из n+1 карты, содержащих m+1 «хороших» карт, то есть C(n+1,m+1).

А раз так, значит мат. ожидание равно C(n+1,m+1)/C(n,m), то есть как раз (n+1)/(m+1). В данном случае, n=52, m=4, так что мат. ожидание равно (52+1)/(4+1)=53/5. Вот, собственно, и всё.

[green_fr]

Ну вот я в своём рассуждении дошёл до суммы r*C и заглох. Без постоянной практики я понимаю, как получается результат, но самому увидеть его не получается.

[turgutmakbak]

Это не самое известное тождество, так что это совершенно нормально. Я тоже повозился какое-то время, пока сообразил. Конечно, вероятностное решение на m.SE намного элегантнее: каждая из n-m ненужных карт предшествует всем m нужным картам с вероятностью 1/(m+1), так что мат. ожидание позиции первой нужной карты — (n-m)/(m+1)+1=(n+1)/(m+1).