Addition of $2$ Events

Question

Let $X$ and $Y$ be independent, each uniformly distributed on $\{1, 2, ..., n\}$. Find $P(X + Y = k)$ for $2 \le k \le 2n$.

\begin{align}P(X + Y = k) &= \sum_{(x,y)\,:\,x+y=k} P(x, y) \\ &= \sum_{(x,y)\,:\,x+y=k} \frac{1}{n^2} \\ &= (k - 1)\frac{1}{n^2} \\ &= \frac{k-1}{n^2} \end{align}

When $k = 2: (1, 1)$

When $k = 3: (1, 2), (2, 1)$

When $k = 4: (1, 3), (3, 1), (2, 2)$

When $k = 5: (1, 4), (4, 1), (2, 3), (3, 2)$

$$\#(x, y) = k - 1$$

Textbook Answer:

$\frac{k-1}{n^2}\,\,\,$ for $\,\,\,2 \le k \le n+1$

$\frac{2n-k+1}{n^2}\,\,\,$ for $\,\,\,n+2 \le k \le 2n$

Why are there $2$ intervals being considered?

Answer 1

Why is there 2 intervals being considered?

Hint: Look what happens if you go "backwards" from $k=2n$ "down":

• $k=2n$: $(n,n)$
• $k=2n-1$: $(n,n-1)$, $(n-1, n)$
• $k=2n-2$: $(n,n-2)$, $(n-1, n-1)$, $(n-2, n)$

etc. What you've got will keep growing with growing $k$, but at some point the number of ways to get the sum $k$ starts shrinking. Thereby the second formula.

Answer 2

We have $x+y = k$ where $x,y \in \{ 1, \ldots, n\}$.

We need not always have $k-1$ pairs of $(x,y)$. In particular, if we let $x=1$, we will need to let $y=k-1$, however, this need not always be possible, as it is possible that $n<k-1$.

If $n\geq k-1$ and $k\geq $, there are $k-1$ pairs, this case has been discussed.

Now, if $k \geq n+2$, the smallest value of $x$ that can be taken would be $x=k-y=k-n$ and the largest value it can take would be $n$. Hence there are a total of $n-(k-n)+1=2n-k+1.$

Answer 3

The first formula fails to find the probability after $n+1$, because:

When $n=2$, the sample space is: $(1,1),(1,2),(2,1),(2,2)$, while $2\le k \le 4$ and $$k=2: (1,1); k=3: (1,2),(2,1); k=4: (2,2)$$ Note that when $k=4$, we are ignoring $(1,3),(3,1)$, because they are not in the sample space. So the two formulas must be applied: one until the middle, another after it.