CJam (8484 80 chars * 0.7 = 58.856)
{_,({_,,{_2$m<(;(+Q0\)\++m>\}%)_(+.{1d2$X2$-*_@+/}1d\1\{1$*\1$-}%)1d\1\-f/.f*z:f*:.+}{,da}?}:Q
Online demoOnline 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