Source: Google Code Jam. https://code.google.com/codejam/contest/10224486/dashboard#s=a&a=1
We're asked to calculate Prob(K successes from N trials) where each of the N trials has a known success probability of p_n.
Some Analysis and thoughts on the problem are given after the Code Jam.
They observe that evaluating all possible outcomes of your N trials would take you an exponential time in N, so instead they provide a nice "dynamic programming" style solution that's O(N^2).
Let P(p#q) = Prob(p Successes after the first q Trials) Then observe the fact that:
Prob(p#q) = Prob(qth trial succeeds)*P(p-1#q-1) + Prob(qth trial fails)*P(p#q-1)
Now we can build up a table of P(i#j) where i<=j, for i = 1...N
That's all lovely - I follow all of this and could implement it.
Then as the last comment, they say:
In practice, in problems like this, one should store the logarithms of
probabilities instead of the actual values, which can become small
enough for floating-point precision errors to matter.
I think I broadly understand the point they're trying to make, but I specifically can't figure out how to use this suggestion.
Taking the above equation, and substuting in some lettered variables:
P = A*B + C*D
If we want to work in Log Space, then we have:
Log(P) = Log(A*B + C*D),
where we have recursively pre-computed Log(B) and Log(D), and A & B are known, easily-handled decimals.
But I don't see any way to calculate Log(P) without just doing e^(Log(B)), etc. which feels like it would defeat to point of working in log space`?
Does anyone understand in better detail what I'm supposed to be doing?