Problem from an old exam:
The random number generator $X$ produces random numbers following a Poisson distribution with parameter $\lambda$. Unfortunately, these numbers are too small, so we decided to create a generator of larger random numbers $Y$ as follows: we write $1$, then $X$ random digits of $0$ and $1$ (each time drawing independently of the result of generator $X$ and the previous digits), and we treat the obtained record as the binary representation of a number. For example, if generator $X$ returns $5$, then generator $Y$ will return a random number between $32$ and $63$.
a) Provide the expected value of the number returned by generator $Y$.
b) Let $X$ generate random numbers with a distribution having the generating function $f_X(t)$ which is defined for all $t \in \mathbb{R}$. Express $EY$ using the generating function $f_X(t)$.
c) Provide the variance of the number returned by generator $Y$ (in the version of the generator from (a)).
My solution for part a)
Let $ Y_i = \begin{cases} Y_i = 2^i, & \text{if the $i$-th bit is set} \\ Y_i = 0, & \text{otherwise} \end{cases} $
and $n$ be the number returned by the generator X, then $$Y = 2^n + \sum_{i=0}^{n-1}Y_i.$$
Therefore, $$\mathbb{E}[Y] = 2^\lambda \sum_{i=0}^{\lambda-1}\mathbb{E}[Y_i] = 2^\lambda+\sum_{i=0}^{\lambda-1}2^i\cdot\frac{1}{2}=2^\lambda+2^{\lambda-1}-\frac{1}{2}$$
This result seems to be correct, because for $\lambda = 5$ it gives $47.5 = \frac{32+63}{2}$
My attempt to solve c)
$$\mathbb{E}[Y^2] = \mathbb{E}\left[(2^n + \sum_{i=0}^{n-1}Y_i)^2\right] = \mathbb{E}\left[4^n+2^{n+1}\cdot\sum_{i=0}^{n-1}Y_i+\left(\sum_{i=0}^{n-1}Y_i\right)\left(\sum_{i=0}^{n-1}Y_i\right)\right] = $$
$$4^\lambda+2^{\lambda+1}\cdot\mathbb{E}[Y] + \sum_{i=0}^{\lambda-1}\mathbb{E}[Y_i \cdot Y_i] + \sum_{i=0}^{\lambda-1}\sum_{\substack{j=0 \\ j \neq i}}^{\lambda-1}\mathbb{E}[Y_i\cdot Y_j]$$
where $$\sum_{i=0}^{\lambda-1}\mathbb{E}[Y_i \cdot Y_i] = \sum_{i=0}^{\lambda-1}(2^i)^2\cdot\frac{1}{2} = \frac{1}{6}(4^\lambda-1)$$
and $$\sum_{i=0}^{\lambda-1}\sum_{\substack{j=0 \\ j \neq i}}^{\lambda-1}\mathbb{E}[Y_i\cdot Y_j] = \sum_{i=0}^{\lambda-1}\sum_{j=0}^{\lambda-1}2^i 2^j \frac{1}{2} \frac{1}{2} - \sum_{i=0}^{\lambda-1}2^i2^i\frac{1}{2}\frac{1}{2} = \frac{1}{4}(2^\lambda-1)^2-\frac{1}{12}(4^\lambda-1).$$
Therefore, $$\mathbb{Var}[Y] = 4^\lambda+2^{\lambda+1}\cdot(2^\lambda+2^{\lambda-1}-\frac{1}{2}) + \frac{1}{6}(4^\lambda-1)+\frac{1}{4}(2^\lambda-1)^2-\frac{1}{12}(4^\lambda-1)-(2^\lambda+2^{\lambda-1}-\frac{1}{2})^2 = \frac{1}{12}(-5\cdot2^{2\lambda+2} + 9\cdot2^{\lambda+1} -1).$$
Unfortunately, this variance is negative.
How can I do part b), and why do I get incorrect variance in part c)?
It’s unclear to me what you did in a). The Poisson parameter $\lambda$ is a real number, so you can’t use $\lambda - 1$ as the upper limit of a sum. Your check on the result is also wrong; the value you got would have been the correct expectation given $X=5$, not $\lambda=5$. It’s not surprising then that the same approach didn’t yield the correct variance.
With probability $\mathrm e^{-\lambda}\frac{\lambda^k}{k!}$ we get $k$ digits after the $1$ and thus a uniformly random number between $2^k$ and $2^{k+1}-1$, with conditional expectation $\frac{2^k+2^{k+1}-1}2=\frac{3\cdot2^k-1}2$, so the expected value is
\begin{eqnarray*} \mathsf E[Y] &=& \sum_{k=0}^\infty\mathrm e^{-\lambda}\frac{\lambda^k}{k!}\frac{3\cdot2^k-1}2 \\ &=& \frac{\mathrm e^{-\lambda}}2\left(3\mathrm e^{2\lambda}-\mathrm e^\lambda\right) \\ &=&\frac{3\mathrm e^\lambda-1}2\;. \end{eqnarray*}
For b), compare
$$ f_X(t)=\sum_{k=0}^\infty P(X=k)t^k $$
with
$$ \mathsf E[Y]=\sum_{k=0}^\infty P(X=k)\frac{3\cdot2^k-1}2 $$
to obtain
$$ \mathsf E[Y]=\frac{3f_X(2)-1}2\;. $$
For c), we’re back to the Poisson distribution, whose generating function is
\begin{eqnarray*} f_X(t) &=& \sum_{k=0}^\infty\mathrm e^{-\lambda}\frac{\lambda^k}{k!}t^k \\ &=& \mathrm e^{-\lambda}\mathrm e^{\lambda t} \\ &=& \mathrm e^{\lambda(t-1)}\;. \end{eqnarray*}
First we can check the result for a):
\begin{eqnarray*} \mathsf E[Y] &=& \frac{3f_X(2)-1}2 \\ &=& \frac{3\mathrm e^{\lambda(2-1)}-1}2 \\ &=& \frac{3\mathrm e^{\lambda}-1}2\;. \end{eqnarray*}
For the variance, we need the variance of the discrete uniform distribution, which is $\frac{n^2-1}{12}$ for a range of $n$ integers. In this case $n=2^X$. Then the total variance is
\begin{eqnarray*} \mathsf{Var}[Y] &=& \mathsf E[\mathsf{Var}[Y\mid X]]+\mathsf{Var}[\mathsf E[Y\mid X]] \\ &=& \mathsf E\left[\frac{4^X-1}{12}\right]+\mathsf{Var}\left[\frac{3\cdot2^X-1}2\right] \\ &=& \frac1{12}\mathsf E\left[4^X\right]-\frac1{12}+\frac94\mathsf{Var}\left[2^X\right] \\ &=& \frac1{12}\mathsf E\left[4^X\right]-\frac1{12}+\frac94\left(\mathsf E\left[4^X\right]-\mathsf E\left[2^X\right]^2\right) \\ &=& \frac73\mathsf E\left[4^X\right]-\frac94\mathsf E\left[2^X\right]^2-\frac1{12} \\ &=& \frac73f_X(4)-\frac94f_X(2)^2-\frac1{12} \\ &=& \frac73\mathrm e^{3\lambda}-\frac94\mathrm e^{2\lambda}-\frac1{12}\;. \end{eqnarray*}
Note that the variance is quite large due to the improbable occurrence of large numbers. For instance, for $\lambda=1$, where most of the numbers only have one or two digits, the variance is already about $30$.