4
$\begingroup$

The following question is from actuarial exam. Let $N$ be uniformly distributed on $\{0,1,2,...,19\}$. Compute $$\mathbb{E}\sum_{k=0}^{N}{N-k \choose k}(-1)^k$$

I started $$\mathbb{E}\sum_{k=0}^{N}{N-k \choose k}(-1)^k=\frac{1}{20}\sum_{n=0}^{19}\mathbb{E}\left(\sum_{k=0}^{N}{N-k \choose k}(-1)^k|N=n\right)=\frac{1}{20}\mathbb{E}\sum_{n=0}^{19}\sum_{k=0}^{n}{n-k \choose k}(-1)^k$$ Here I changed summation variable and the order of summation a couple of times but it didn't work: $$\frac{1}{20}\mathbb{E}\sum_{n=0}^{19}\sum_{k=0}^{n}{n-k \choose k}(-1)^k=\frac{1}{20}\mathbb{E}\sum_{n=0}^{19}\sum_{l=0}^{n}{l \choose n-l}(-1)^{n-l}=\frac{1}{20}\mathbb{E}\sum_{l=0}^{19}\sum_{n=l}^{19}{l \choose n-l}(-1)^{n-l}=\frac{1}{20}\mathbb{E}\sum_{l=0}^{19}\sum_{m=0}^{19-l}{l \choose m}(-1)^{m}$$

The last sum is equal $0$ if $l\leq 9$. This is because $$\sum_{k=0}^{n}{n \choose k}(-1)^k=0.$$ Hence $$\frac{1}{20}\mathbb{E}\sum_{l=0}^{19}\sum_{m=0}^{19-l}{l \choose m}(-1)^{m}=\frac{1}{20}\mathbb{E}\sum_{l=10}^{19}\sum_{m=0}^{19-l}{l \choose m}(-1)^{m}$$

I also tried to count this sum by setting consecutive $N=0,1,2,3,4...$ but I coudn't find any regularity.

Please help

$\endgroup$
4
$\begingroup$

We have the sum $$\begin{align*} \frac1{20}\sum_{n=0}^{19}\sum_{k=0}^n\binom{n-k}k(-1)^k&=\frac1{20}\sum_{k=0}^{19}(-1)^k\sum_{n=k}^{19}\binom{n-k}k\\&=\frac1{20}\sum_{k=0}^{19}(-1)^k\binom{20-k}{k+1}\tag{*}\\&=\frac1{20}\sum_{k=0}^{19}(-1)^k[z^{k+1}](1+z)^{20-k}\tag{**}\\&=\frac1{20}\sum_{k=0}^{\infty}(-1)^k[z^{k+1}](1+z)^{20-k}\\&=\frac1{40\pi i}\sum_{k=0}^{\infty}(-1)^k\int_{|z|=r}\frac{(1+z)^{20-k}}{z^{k+2}}dz\tag{***}\\&=\frac1{40\pi i}\int_{|z|=r}\frac{(1+z)^{20}}{z^2}\frac{1}{1+\frac{1}{z(1+z)}}dz\\&=\frac1{40\pi i}\int_{|z|=r}\frac{(1+z)^{21}}{z(z^2+z+1)}dz\\&=\frac{1}{20}\sum_i \text{res}_{z=z_i}\frac{(1+z)^{21}}{z(z^2+z+1)}. \end{align*}$$ $(*)$ : Hockey stick identity is used.
$(**)$ : $[z^n]f(z)$ denotes the $n$-th coefficient $a_n$ of $f(z)=\sum_{i=0}^\infty a_iz^i$.
$(***)$ : $\int_{|z|=r} z^k dz=2\pi i \mathbf{1}_{k=-1}$ is used and $r>1$ is chosen sufficiently large so that the geometric sum converges.

Now, we can see that $\frac{(1+z)^{21}}{z(z^2+z+1)}$ has simple poles at $z=0$, $z= e^{\pm2\pi i/3}= \omega,\bar \omega$. The residues are $$ \text{res}_{z=0}\frac{(1+z)^{21}}{z(z^2+z+1)}=\lim_{z\to 0}\frac{(1+z)^{21}}{z^2+z+1}=1, $$ $$ \text{res}_{z=\omega}\frac{(1+z)^{21}}{z(z^2+z+1)}=\lim_{z\to \omega}\frac{(1+z)^{21}}{z(z-\bar\omega)}=\frac{(\omega+1)^{21}}{\omega(\omega-\bar\omega)}=\frac{-\bar\omega^{21}}{\omega(\omega-\bar\omega)}=\frac{-1}{\omega(\omega-\bar\omega)}, $$$$ \text{res}_{z=\bar\omega}\frac{(1+z)^{21}}{z(z^2+z+1)}=\lim_{z\to \omega}\frac{(1+z)^{21}}{z(z-\omega)}=\frac{(\bar\omega+1)^{21}}{\bar\omega(\bar\omega-\omega)}=\frac{-\omega^{21}}{\bar\omega(\bar\omega-\omega)}=\frac{-1}{\bar\omega(\bar\omega-\omega)}. $$ Summing residues, we get $$ 1-\frac1{\omega-\bar\omega}(\frac{1}{\omega}-\frac{1}{\bar\omega})=1+\frac1{\omega\bar\omega}=2. $$ So we have that the expectation is equal to $\frac{2}{20}=\frac{1}{10}.$ (Note: the result can be confirmed by wolframalpha.)

$\endgroup$
4
$\begingroup$

In the book 'Concrete Mathematics' of Ronald L.Graham, Donald E.Knuth and Oren Patashnik you can find the value of $$ R_m=\sum_{k\leq m}\binom{m-k}{k}(-1)^k. $$ Look at paragraph 5.2, Problem 3.

The authors shows that for $m\geq 2$ $$ R_m=R_{m-1}-R_{m-2} $$ and finally got $$ R_m=\begin{cases}\hphantom{-}1, & m \mod 6 = 0 \cr \hphantom{-}1, & m \mod 6 = 1 \cr \hphantom{-}0, & m \mod 6 = 2 \cr -1, & m \mod 6 = 3 \cr -1, & m \mod 6 = 4 \cr \hphantom{-}0, & m \mod 6 = 5\end{cases} $$ So the random variable $X(N)=\sum_{k=0}^{N}{N-k \choose k}(-1)^k$ can take only three values. And $$\mathbb P(X(N)=-1)=\mathbb P(N\in\{3,4,9,10,15,16\})=0.3,$$ $$\mathbb P(X(N)=0)=\mathbb P(N\in\{2,8,14,5,11,17\})=0.3,$$ $$\mathbb P(X(N)=1)=\mathbb P(N\in\{0,1,6,7,12,13,18,19\})=0.4.$$ So the expectation can be computed.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.