This is a problem that I am to write an algorithm for I do n

This is a problem that I am to write an algorithm for. I do not need help with the code part, but if someone could give me a good explanation of the domain of the problem, that would be greatly appreciated.

coinFlips is a function that, given a vector of n values in the range [0, 1] will return the probability of Player 2 winning the game described below outright.

Thanks for the help!

Solution

ci = Probability of head for coin i. (Point for player 1)

1-ci = probability of tail for coin i (point fot player 2)

Player 2 wins if he/she wins all the n games or any n-1 games or any n-2 games, and so, on till n/2+1 games.

Therefore, probability of player 2 winning = ⁿC_n(1-c_i)ⁿ + ⁿC_n-1(1-c_i)^n-1c_i + ... ⁿC_n/2+1(1-c_i)^n/2+1c_i^n/2-1

This could be computed using properties of binomial if ci were same but since they are different we will need to calculate them for each value sets.

Hence, an easier way to do it with a computer is to simulate.

Algorithm:

result = 0

player1_wins = 0

player2_wins = 0

coinFlips(prob)

for k in range(0,10000): #just simulating the game 10,000 times to get an approximation of the probability

for i in range(0, n):

    if rand(0,1)<prob(i):

        player1_wins ++

    else:

        player2_wins ++

if player2_wins>player1_wins:

    result ++

Final probability = result/10000