Knockout probabilities

Question

Knockout is a basketball game where players take turns shooting. It is played as a sequence of two-player contests, each of which has the possibility of "knocking out" one of those players.

Suppose the players are A B C D and their chances of shooting and making a basket are 0.1 0.2 0.3 0.4 respectively, independently of the other player in the contest. The two players at the front of the line, A and B, "fight." Since A goes first, he is the defender, in danger of being eliminated, and B is the attacker, and not in danger of immediate elimination. A shoots first. If A makes it, A has successfully defended, and goes to the back of the line. The line would change to B C D A. If A doesn't make it, then B shoots. If B makes it, then A is out and B goes to the back of the line, so the line becomes C D B. If neither A nor B makes it, the process repeats, with A shooting again, until either A or B makes a basket.

Suppose the line changed to B C D A (A had successfully defended). Now, B and C "fight," with B being the defender, and C being the attacker. This process repeats until only one person is left over. That person is the winner.

Your task is to calculate the probabilities of each person winning given the chance that they will make a basket.

Input:

A list of numbers, such as 0.1 0.2 or 0.5 0.5 0.5 0.5, where the nth number is the chance that the nth player will make a basket. You can take this input in any format you like, including as the parameters to a function.

Output:

A list of numbers, where the nth number is the chance that the nth player will win the game. Your numbers must be accurate to at least two decimal places at least 90% of the time. This means that you can use a simulation-based approach. However, if your code is not simulation based (it is guaranteed to return a correct answer to at least 6 decimal places) then take away 30% from your score.

Example between 0.5 0.5: Call the players A and B. Let p be the probability of A winning. A has a 2/3 chance of successfully defending (since there's a 1/2 chance that A scores, a 1/4 chance that A misses and B scores, and a 1/4 chance that both miss and the process repeats). If A fails to defend, he is knocked out and B wins. If A defends, then the line becomes B A. Since the situation is symmetric, the probability of A winning is (1 - p). We get:

p = 2/3 * (1 - p) + 1/3 * 0. Solving, we get p = 2/5. The output should be 2/5 3/5 or 0.4 0.6.

I'm not good enough with probability to do more complex examples.

If you need more test cases, here are a few:

0.1 0.2 0.3 0.4 --> 0.01 0.12 0.25 0.62
0.99 0.99 --> 0.5 0.5 (it's not exact, but if you round to two decimal places, you get 0.5 and 0.5)

Answer 1

CJam (84 80 chars * 0.7 = 56)

{_,({_,,{_2$m<(;(+Q0\)\++m>\}%)_(+.{X2$-*_@+/}1\{1$*\1$-}%)1\-f/.f*:.+}{,da}?}:Q

Online demo. This is a recursive function which takes an array of doubles and returns an array of doubles. The online demo includes a tiny amount of scaffolding to execute the function and format the output for display.

Dissection

The basic principle is that if there are n > 1 players left, one of them must be the next one to be knocked out. Moreover, the order of the queue after that happens depends only on the initial order of the queue and on who gets knocked out. So we can make n recursive calls, calculate the winning probabilities for each player in each case, and then we just need to weight appropriately and add.

I'll label the input probabilities as [p_0 p_1 ... p_{n-1}]. Let f(a,b) denote the probability that a fails to defend against b. In any given round, the probability that a defends successfully is p_a, the probability that b knocks a out is (1-p_a)*p_b, and the probability that it goes to another round is (1-p_a)*(1-p_b). We can either do an explicit sum of a geometric progression or we can argue that the two geometric progressions are proportional to each other to reason that f(a,b) = (1-p_a)*p_b / (p_a + (1-p_a)*p_b).

Then we can step up a level to full rounds of the line. The probability that the first player is knocked out on is f(0,1); the probability that the second player is knocked out is (1-f(0,1)) * f(1,2); the third player is (1-f(0,1)) * (1-f(1,2)) * f(2,3); etc until the last one is knocked out with probability \prod_i (1-f(i,i+1)) * f(n-1,0). The same argument about geometric progressions allows us to use these probabilities as weights, with normalisation by a factor of 1 / \prod_i f(i, i+1 mod n).

{                   e# Define a recursive function Q
  _,({              e# If we have more than one person left in the line...
    _,,{            e#   Map each i from 0 to n-1...
      _2$m<         e#     Rotate a copy of the probabilities left i times to get [p_i p_{i+1} ... p_{n-1} p_0 ... p_{i-1}]
      (;(+          e#     i fails to defend, leaving the line as [p_{i+2} ... p_{n-1} p_0 ... p_{i-1} p_{i+1}]
      Q             e#     Recursive call
      0\)\++        e#     Insert 0 for the probability of i winning and fix up the order
      m>\           e#     Rotate right i times and push under the list of probabilities
    }%
    )               e#   Stack: [probs if 0 knocked out, probs if 1 knocked out, ...] [p_0 p_1 ...]
    _(+.{           e#   Duplicate probs, rotate 1, and pointwise map block which calculates f(a,b)
      X2$-*_@+/     e#     f(a,b) = (1-p_a)*p_b / (p_a + (1-p_a)*p_b)  TODO is the d necessary?
    }
    1\{1$*\1$-}%    e#   Lift over the list of f(a,b) a cumulative product to get the weights  TODO is the d necessary?
    )1\-f/          e#   Normalise the weights
    .f*             e#   Pointwise map a multiplication of the probabilities for each case with the corresponding weight
    :.+             e#   Add the weights across the cases
  }{,da}?           e# ...else only one left, so return [1.0]
}:Q