[Task 80] explanation on authors notes on the problem ?
Back to Problem Solutions forum
My understanding of the problem is this:
the chance to win/survive for A is not an exact number, but just an approximation with the formula (excerpt from my own solution):
# given a='A hits', an='A does not hit', bn='B does not hit', compute:
# prob =~ a OR (an AND bn AND a) OR (an AND bn AND an AND bn AND a) OR ...
# => prob =~ a + an*bn*a + an*bn*an*bn*a + ...
so basically you aggregate the probability with this sum of products until the next summand gets sufficiently small.
But the author starts with this assumtion:
# pX = pA + pAlandMisses * pBobAlsoMisses * pX
I don't get why the probability to survive (pX) is contained in the product on the right hand side.
Anyway, approximating the sum of products from above seems sufficient, only problem is that I seem to get a rounding error for the second example input. I think that because the sum is approaching 62.5 from below, this is somehow stored within the float (even though print shows '62.5') but rounding it yields 62.0, not 63.0. For the random input data, I seem to get the correct results, though (Python).
Since I didn't find anything else, does somebody care to explain the proposed solution a little bit ? Thanks!
The approximation is fine in this instance and a quick way to get the answer using iteration.
The exact answer is derived via: (Using the same notation as the question and pB' equals (1-pB) for brevity)
As you stated:
pX = pA + (pA' * pB' * pA) + (pA' * pB' * pA' * pB' * pA) + (pA' * pB' * pA' * pB' * pA' * pB' * pA) + ...
Factoring out pA' and pB'
pX = pA + (pA' * pB' * (pA + (pA' * pB' * pA) + (pA' * pB' * pA' * pB' * pA) + ...)
Substitute in pY into the above equation
pX = pA + (pA' * pB' * pY)
where
pY = pA + (pA' * pB' * pA) + (pA' * pB' * pA' * pB' * pA + ...
Since this is an infinite series, pY = pA, so replacing pY in the 3rd equation with pA gives
pX = pA + (pA' * pB' * pA)
which is what the author started with.
Sorry that last part should be:
Since this is an infinite series, pY = pX, so replacing pY in the 3rd equation with pX gives
pX = pA + (pA' * pB' * pX)
which is what the author started with.
thanks for the explanations :)