Did I do this convolution problem correct?

romsek

MHF Helper
Nov 2013
6,727
3,030
California
I can't make heads or tails of your chicken scratch :p

This is a tricky problem. It needs care and neatness.

Don't forget both distribution sequences are finite.
 

romsek

MHF Helper
Nov 2013
6,727
3,030
California
I'm seeing that

$c(n) = \begin{cases}
\sum \limits_{k=0}^n \dbinom{N}{k}p^k (1-p)^{N-k} \dbinom{M}{n-k}p^{n-k} (1-p)^{M-n+k}&0\leq n \leq M\\
\sum \limits_{k=n-M}^n \dbinom{N}{k}p^k (1-p)^{N-k} \dbinom{M}{n-k}p^{n-k} (1-p)^{M-n+k}&M+1 \leq n \leq N+M
\end{cases}$

we can clean that up a bit

$c(n) = p^n (1-p)^{N+M-n}\sum \limits_{k=\ell}^n \dbinom{N}{k}\dbinom{M}{n-k}$

where $\ell = \begin{cases}0 &0\leq n \leq M\\n-M &M+1\leq n \leq N+M\end{cases}$
 

romsek

MHF Helper
Nov 2013
6,727
3,030
California
$c(n) = p^n (1-p)^{N+M-n}\sum \limits_{k=\ell}^n \dbinom{N}{k}\dbinom{M}{n-k}$

where $\ell = \begin{cases}0 &0\leq n \leq M\\n-M &M+1\leq n \leq N+M\end{cases}$
Ideally we'd like to show that the sum is equal to $\dbinom{N+M}{n}$.

I confess I haven't been able to do that.
 
Jul 2015
605
15
United States
why is M+1 < n < M+N
Where do we get this boundary? I follow everything else.
 
Jul 2015
605
15
United States
I guess also, o<n<M as well.

So basically, you are telling me that, If n is between 0 and or equal to M, then we get 0.... why?
 

romsek

MHF Helper
Nov 2013
6,727
3,030
California
I guess also, o<n<M as well.

So basically, you are telling me that, If n is between 0 and or equal to M, then we get 0.... why?
no.. where do you get that from?

The sum has to be treated differently for the cases $0 \leq n \leq M$ and $M+1 \leq n \leq M+N$

You have two sequences that you are basically dotting one another with. One is stationary, the other is flipped in index and slid one step at a time to the right.
For $0 \leq n \leq M$ the flipped sequence is $0$ for $k > n$. At $n = M$ the entire flipped sequence now does intersect with the entire stationary sequence.

Then at $n=M+1$ the flipped sequence starts being $0$ at the beginning of the sum. It only has $M$ non-zero values.

I see I've got a mistake in the formula. The stationary sequence values are zero for $k > N$ so the sum should be

$c(n) = \begin{cases}
\sum \limits_{k=0}^n \dbinom{N}{k}p^k (1-p)^{N-k} \dbinom{M}{n-k}p^{n-k} (1-p)^{M-n+k}&0\leq n \leq M\\
\sum \limits_{k=n-M}^n \dbinom{N}{k}p^k (1-p)^{N-k} \dbinom{M}{n-k}p^{n-k} (1-p)^{M-n+k}&M+1 \leq n \leq N\\
\sum \limits_{k=n-M}^N \dbinom{N}{k}p^k (1-p)^{N-k} \dbinom{M}{n-k}p^{n-k} (1-p)^{M-n+k}&N+1 \leq n \leq M+N
\end{cases}$

Let me see if I can gen up some pictures for you.
 

romsek

MHF Helper
Nov 2013
6,727
3,030
California
Ok, 4 regions of interest. The first picture is $n=0$ to get you oriented.

Clipboard01.jpg

The sliding sequence, red, is reversed with it's last element occurring at 0. The stationary sequence, blue, starts at 0.

Next we have $n=5$ We start the sum at 0, and we end it at $n$ This is because the stationary sequence is 0 prior to 0
and the sliding sequence is 0 after $n$

Clipboard02.jpg

Next we have $n=15$ where the end of the sliding sequence is now past 0.

Clipboard03.jpg

We sum from $n-M$ to $n$ as the sliding sequence is 0 prior to and after these indices.

Finally we have $n=21$ where the leading part of the sliding sequence has slid past the end of the stationary sequence.

Clipboard04.jpg

Here we sum from $n-M$ to $N$ because the stationary sequence is 0 after that.

I don't suppose you have Mathematica do you?
 
  • Like
Reactions: math951