Как максимально увеличить общую вероятность?

Question

Я хочу максимизировать общую вероятность выигрыша в игре со случайным выбором, в которую играют следующим образом:

У меня есть n лотерейных билетов, и из этих n только 1 - счастливый билет, теперь у меня есть2 вариант: либо нарисовать билет, либо попросить мастера удалить несколько незадачливых билетов из общего количества билетов, X должно быть кратным k (доступно), а X должно быть меньше общего количества билетов.

Если яНарисуйте неудачливого мастера билетов, который добавит к неудачным билетам к пачке билетов.

У нас есть максимум м ходов, каждый из которых является одним из следующих

1. Либо мы рисуембилет
2. Либо мы просим мастера удалить X билетов (X кратно k)

Я хочу максимизировать вероятность.

И вывести общую вероятностьP / Q как P * Q ^ (- 1) где Q является модульной обратной величиной Q.

После наблюдения и игры я думаю, что общая вероятность будет максимальной только тогда, когда мы будем играть в игру следующим образом

1. Первым ходом мы рисуем билет, и вероятность выигрыша равна 1 / n.

2. Если мы рисуем неудачный билет, в первый ход добавляются k билетов, и мы можемпопросите мастера убрать k билетов за второй ход.

3. На третьем ходу мы снова разыграем билет и вероятность выигрыша теперь равна
   ((n-1) / n) * (1 / n).

Точно так же, если есть m ходов, мы можем сделать вывод, что общая вероятность выигрыша равна (1 - ((n-1) / n) ^ r), гдемы можем найти значение r

n

, например: n = 3 k = 20 m = 3

полная вероятность 1- (2/3) ^ 2 = 5/9

n = 5 k = 7 м = 1

общая вероятность выигрыша = = 1/5

Окончательный результат:

5 * (9)^ (- 1)% 1000000007 = 555555560

1 * (5) ^ (- 1)% 1000000007 = 400000003

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

мы снова положили билет, который мы выбрали, снова в колоду, поэтому после неправильного рисования мы имеем n + k вместо n + k-1, а также n

РЕДАКТИРОВАТЬ: Доказательство моей стратегии

для каждого предпринятого нами хода есть 2 возможности

либо мы получаем 1 / n* (n-1) / n или мы получаем (n-1) / n * (1 / n + k) + (n-1 / n) ((n + k-1) / n + k) (1 / n + 2 * k)

теперь, после решения обеих сторон, мы получим уравнение 1 / n слева, а справа - (2 * n + 3 * k-1) / ((n + 2 * k) * (n + k) и я обнаружил, что RHS всегда меньше или равен RHS

Так что после дальнейшего решения я получаю LHS как 2 * (k ^ 2) и RHS как n ^ 2-n и как задано n

Следовательно, доказано.

Пожалуйста, предоставьте отзыв для доказательства.

Answer 1

Ваша стратегия неверна.После получения незадачливого билета вы попросили мастера удалить k билетов, но если бы вы начали , играя в точно таком же состоянии, вы бы выбрали билет.Это не имеет смысла, потому что игра не помнит ваши предыдущие ходы, и поэтому текущая ситуация всегда должна диктовать лучший выбор.

Пусть P (n, m, k) вероятность выигрыша с n билетами, макс. m ходов и k с оптимальной стратегией.

Если вы выбираете билет,тогда вероятность равна 1 / n + P (n + k-1, m-1, k) * (n-1) / n .

Если вы этого не сделаете,вероятность составляет P (nk, m-1, k)

Оптимальным вариантом является тот, который имеет наибольшую вероятность, и поэтому:

P (n,m, k) = max (1 / n + P (n + k-1, m-1, k) * (n-1) / n, P (nk, m-1, k))

Вы можете вычислить это рекурсивно, с запоминанием, поскольку, вероятно, есть перекрывающиеся подзадачи, то есть с динамическим программированием.