dimanche 3 février 2019

How to maximize the total probability?

I want to maximize the total probability of winning in a game of random selection which is played as follows,

I have n lottery tickets and out of these n only 1 is the lucky ticket, now I have 2 option either draw a ticket or ask the master to remove some X unlucky ticket out of total tickets, X must be a multiple of k (available) and X must be smaller than total number of tickets.

If i draw an unlucky ticket master will add k unlucky tickets to the pile of tickets.

We have at max m moves to play, each move is one of the following

  1. Either we draw a ticket
  2. Either we ask master to remove X tickets (X is multiple of k)

I want to maximize the probability.

And output the total probability P/Q as P*Q^(-1) where Q is modular inverse of Q.

After observing and playing the game I think the total probability will be maximum only when we play the game in the following way

  1. First move we draw a ticket and probability of winning is 1/n.

  2. If we draw an unlucky ticket in first move k tickets are added and we can ask the master to remove k tickets in second move.

  3. In third move we again draw ticket and probability of winning now is
    ((n-1)/n)*(1/n) .

Similarly if there are m moves than we can conclude that, total probability of winning is (1-((n-1)/n)^r) where we can find value of r

for example : n = 3 k = 20 m = 3

total probability is 1-(2/3)^2 = 5/9

n = 5 k = 7 m = 1

total probability of winning is = 1/5

Final output :

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

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

If there is other winning strategy in this game please provide it with proof and i don't have a proof for my strategy too so if you can prove my strategy i will be glad to have it as well as a psuedocode will help me to proceed.




Aucun commentaire:

Enregistrer un commentaire