https://codeforces.me/problemset/problem/1540/B
refer to the tutorial of this problem which provides a solution to the following problem using dp in o(A * B) and later on i'll provide a o(A + B) solution that works but i need your help in proving it
the problem : given two numbers A and B each second one of them is choosen with chance 1 / 2 each (equiprobable) and decreased by 1 , if one of the numbers reachs 0 the other is choosen with probability 1 until it reachs zero then we are done , find the probability that A reachs 0 before B
again for the o(A * B) solution refer to the tutorial
now the reason we cant just calculate the favourable outcome and divide it by total outcome is because not all outcomes have the same probability as the events and dependent such that whenever one of them reachs 0 the probability of choosing the other one is 1 afterwards but lets look at a different problem imagine u are going to make A + B picks and pick A or B equiprobable , find the probability that you pick A , A times before picking B , B times , we are not decreasing anything here and can pick A (A + B) times now if we think about this problem for a bit we realize that the same dp solution represented in the tutorial solves this one but instead this problem has a combinatorial solution in o(A + B) because all paths have the same probability as both events and independent and picking A however many times doesnt change the chance of picking B so now we have both problems that share a dp solution but one of them offers a combinatorial solution which we can use for the first one how do we prove that this combinatorial approach works for the first problem ?
heres the submission using the combinatorial approach 279326895
the combinatorial approach is relatively easy but if anybody wants me to explain it just comment below
Only read your short description of the problem, but this looks like you can just sum over the negative binomial distribution (how many trials needed until A'th success, sum from A to A+B-1). Should be O(A+B).
not sure if i fully understand you but its not the same problem you described because the events and dependent if one of A or B reachs zero u cant choose it anymore and the other is choosen with probability 100% i'll add this to the blog for clarifications
Had a look at the problem. What I described above works in $$$O(A+B)$$$ per query, but for the problem you need to precompute the entire table for $$$0 \le A,B \le n$$$, which can be done in $$$O(n^2)$$$ (using the dp approach described in tutorial). The $$$O(A+B)$$$ per query approach takes $$$O(n^3)$$$ to build the entire table (still works for this problem though).
We have that $$$P[A \text{ chosen } a \text{ times before } B \text{ chosen } b \text{ times}] = \sum_{j=a}^{a+b-1} P[X = j] = \sum_{j=a}^{a+b-1} \binom{j-1}{b-1} \cdot 2^{-j}$$$ where $$$X \sim NB(a, 1/2)$$$ as (replacing A,B by 1,0) \begin{align} P[\text{a 1's before b 0's}] &= \sum_{j=1}^\infty P[\text{a 1's before b 0's} | \text{a'th 1 at position j}] \cdot P[\text{a'th 1 at position j}] \newline &= \sum_{j=1}^\infty P[\text{at most b-1 0's before position j} | \text{a'th 1 at position j}] \cdot P[\text{a'th 1 at position j}] \newline &= \sum_{j=1}^{\infty} P[\text{at most b-1 0's before position j}] \cdot P[\text{a-1 1's before position j}] \cdot P[\text{1 at position j}]\newline &= \sum_{j=a}^{a+b-1} P[\text{a-1 1's, j-1-(a-1) 0's in first j-1 positions}] \cdot \frac{1}{2} \newline &= \sum_{j=a}^{a+b-1} \binom{j-1}{a-1} \cdot (1/2)^{a-1} \cdot (1/2)^{j-1-(a-1)} \cdot \frac{1}{2} \quad \text{(Binomial distribution)} \newline &= \sum_{j=a}^{a+b-1} \binom{j-1}{a-1} \cdot (1/2)^{j}. \end{align} The term in the second line is already $$$P[X=j]$$$ where $$$X\sim NB(a,1/2)$$$, the remaining is only deriving negative binomial distribution.
i read this and with simple algebra i realized it would be the same problem if u could choose infinitely many As or Bs
Auto comment: topic has been updated by Axial-Tilted (previous revision, new revision, compare).