I was going through a set of problems at codeforces.com, I came across a very interesting question (link: https://codeforces.com/contest/312/problem/B):
Question:
SmallR is an archer. SmallR is taking a match of archer with Zanoes. They try to shoot in the target in turns, and SmallR shoots first. The probability of shooting the target each time is a/b for SmallR while for Zanoes its c/d. The one who shoots in the target first should be the winner. Output the probability that SmallR will win the match.
Testcase:
INPUT: 1 2 1 2
OUTPUT: 0.66667
My approach:
Assume,
p= probability of SmallR winning = a/b.
q = probability of Zanoes winning = c/d.
for the given inputs (1,2,1,2) are values of a,b,c,d respectively, p becomes 1/2 and q becomes 1/2.
possible scenarios are as follows:
SmallR wins the first turn = p = 1/2
SmallR wins the second turn =$$(1-p)*(1-q)*p$$ Since to reach 2nd turn SmallR should've missed the first turn target, Zanoes missed his target in his turn, Thus SmallR wins in his second turn by hitting the target.
SmallR wins the third turn = $$ (1-p)^2 * (1-q)^2 * p $$ To reach 3rd turn SmallR must've missed the first target in first turn, Zanoes missed his target in his turn, SmallR missed his target again in his 2nd turn, Zanoes misses his target too, Thus SmallR successfully shoots and wins in his 3rd turn.
From the following pattern we can say the probability of SmallR winning the K-th round will be, $$ (1-p)^k * (1-q)^k * p $$.
taking p as common we can find the sum of all probabilities as, $$ W = p[1+(1-p)(1-q)+(1-p)^2 (1-q)^2+.....+(1-p)^n (1-q)^n]$$
Applying infinite progression formula: $$W = (p)/(1-(1-p)*(1-q))$$, substituting p = 1/2 and q = 1/2 we get W = 0.66667.
This answer looks counter-intuitive to me, The same answer appears if we assume Zanoes wins. Shouldn't the answer be 50-50 or 0.5 which makes more sense given their success ratios.
Please help me understand the solution, I'm really perplexed. Thankyou!
The reason the probabilities are different is because SmallR goes first. If the Zanoes went first, they would also have a $\frac{2}{3}$ chance of winning.
Think about it - SmallR goes first and already has a $\frac{1}{2}$ chance of winning, plus some extra chance if both SmallR and Zanoes lose their first round. Therefore, SmallR's probability will be greater than $\frac{1}{2}$, and Zanoes's proability is less than $\frac{1}{2}$.
-FruDe