Probability interview question

Question

Suppose we have three positive integers $A, B, C$. We randomly choose an integer $a$ in the range $[0,A]$ and an integer $b$ in the range $[0,B]$. Find the probability that $a + b\leq C$.

I am unable to proceed in this question. Any hints .

Answer 1

Assuming that each integer in given range has the same probability to be choosen, you have to count the cases when the inequality holds and divide it by all cases, namely: $$ \frac{\sum_{a=0}^A\sum_{b=0}^B\mathbf{1}(a+b\leq C)}{(A+1)\cdot (B+1)} $$ where $\mathbf{1}(P)=1$ if proposition $P$ is true and $\mathbf{1}(P)=0$ otherwise.

Answer 2

Let $S_C$ be the number of couples $(a,b)$, $a\in [0,A]$ and $b\in [0,B]$ such that $a+b \leq C$. It is clear that $S_0=1$ because the only couple that can sum up to zero is $(0,0)$. Moreover if $C>A+B$ then $S_C=S_{A+B}$ since all couples that are counted in $S_C$ were already counted in $S_{A+B}$. Without loss in generality we can assume that $A\leq B$. Let us study the function $T_C=S_{C+1}-S_C$. It corresponds to the number of couples $a,b$ where $a+b=C$. This is easier to count , e.g. if A and B are big enough then for $T_3$ we count the couples $(3,0), (2,1), (1,2)$ and $(0,3)$. In fact we can conclude easily then for $C$ small enough we have $T_C=C+1$. But this only works if $C \leq A$. Once $C>A$ we must start off with $(A,C-A),(A-1,C-A+1),\ldots,(0,C)$ (on the condition that $B$ is big enough so that $C-A \in [0,B]$). In this case we will have $T_C=A+1$. But this can not continue forever since in case $C>B$ we will not even arrive to $(0,C)$ but only to $(C-B,B)$. We conclude that for $C>B$ we have $T_C=A+B-C+1$ so globally we have :$$T_C = \begin{cases} C+1, & \text{for $C \leq A$} \\ A+1, & \text{for $A \leq C \leq B$}\\ A+B-C+1, & \text{for $B \leq C \leq A+B+1 $}\\ 0, & \text{for $A+B+1 \leq C $}\\ \end{cases} $$ To reconstruct $S$ all we have to do is to "integrate" this function over the different domains. A bit of calculation gives: $$S_C = \begin{cases} C(C+1)/2, & \text{for $C \leq A$} \\ A(A+1)/2+(A+1)(C-A), & \text{for $A \leq C \leq B$}\\ f(C), & \text{for $B \leq C \leq A+B+1 $}\\ (A+1)(B+1) & \text{for $A+B+1 \leq C $}\\ \end{cases} $$ Where $f(C)=(A+1)(B+1)-(A+B+1-C)(A+B+1-C+1)/2$.

Answer 3

Can be done in $\min(O(A\log B),O(B\log A))$ using binary serach.

Answer 4

If $a$ and $b$ are independent there is a very simple solution. First convince yourself that $$a + b \leq C \Leftrightarrow \mathrm{max}(a,b) \leq \frac{C}{2}$$

Then due to independence, $P\{\mathrm{max}(a,b) \leq \frac{C}{2}\} = P\{a \leq \frac{C}{2}\}P\{b \leq \frac{C}{2}\}$

I am assuming both $a$ and $b$ have uniform distributions. Then, $P\{a \leq \frac{C}{2}\} = \frac{\lfloor\frac{C}{2}\rfloor+1}{A+1}$. Likewise, $P\{b \leq \frac{C}{2}\} = \frac{\lfloor\frac{C}{2}\rfloor+1}{B+1}$. Therefore,

$$P\{a + b \leq C\} = \frac{\left(\lfloor\frac{C}{2}\rfloor+1\right)^2}{(A+1)(B+1)}$$

I made the implicit assumption that $A$ and $B$ are larger than $\frac{C}{2}$. But I guess it is clear how you would adapt the solution for the cases not covered by this assumption.