Unconditioned Expectation $E[S]$ from $E[S|X=k]$?

Question

Let $X =$ the number of requests you receive at your web site per minute, where $X \sim Poi(10)$. Each request, independently of all other requests, is equally likely to be routed to one of $N$ web servers. Compute the expected number of web servers that will receive at least one request each during a minute.

(Hint: there are a few ways to do this problem, but one way you might approach it is to first determine the conditional expectation of the number of web servers that receive at least one request each during a minute, conditioned on some fixed number, k, of requests during that minute. Then use that result to compute the unconditional expectation of the number of web servers that receive at least one request each during a minute.)

Have tried many things:

Defined $S = \sum_i S_i$

Defined $S_i =$ at least $1$ request sent to server $i$

$$P(S_i \ge 1 | k) = 1 - P(Si = 0) = 1 - \left(\binom{k}{0} \left(\frac1N\right)^0 \left(1 - 1/N\right)^k\right)$$

$$E[S_i | k] = P(S_i \ge 1) $$

$$E[S] = E[S | X = k] P(X = k)$$

$$E[S|k] = N E[S_i|k]$$

$$E[S] = \sum_k (N E[S_i|k] P(X=k)) $$

But stuck

Answer 1

For convenience, let $r=1-\frac1N,$ \begin{align} E[S]&= \sum_{k=0}^\infty N E[S_i|X=k]P(X=k)\\ &=N\sum_{k=0}^\infty \left(1- r^k \right)P(X=k)\\ &=N\left( 1- \sum_{k=0}^\infty r^kP(X=k)\right)\\ &=N\left( 1- \sum_{k=0}^\infty r^k\exp(-\lambda )\frac{\lambda^k}{k!}\right)\\ &=N\left( 1- \exp(-\lambda )\sum_{k=0}^\infty \frac{(r\lambda)^k}{k!}\right)\\ &=N\left( 1- \exp(-\lambda )\exp(\lambda r)\sum_{k=0}^\infty\exp(-\lambda r) \frac{(r\lambda)^k}{k!}\right)\\ &=N\left( 1- \exp(\lambda (r-1))\right)\\ &=N\left( 1- \exp(-\frac{\lambda}{N})\right)\\ \end{align}

Answer 2

I'm sure someone else will mention the tower rule of expectations; however, I think a poisson thinning approach is also illuminating given that thinking of requests and routing as a poisson process is more fruitful and more natural.

For the entire process, requests arrive at a rate of:

$$\lambda = 10$$

By poisson thinning, requests arrive at each server $n$ according to a poisson process at a rate of:

$$\lambda_n = \frac{10}{N}$$

This means that the probability any server gets at least one request is:

$$P(\text{$server$ $n$ has a request}) = 1 - P(\text{$server$ $n$ has $0$ requests})$$

$$P(\text{$server$ $n$ has $0$ requests}) = e^{-\frac{10}{N}}$$

$$P(\text{$server$ $n$ has a request}) = 1 - e^{-\frac{10}{N}}$$

$$$$

Now, for the expected number of servers with at least one request.

$$E[S] = E[\sum_{n=1}^{N}\mathbb{1}\{\text{$server$ $n$ received at least one request}\}]$$ $$= \sum_{n=1}^{N}E[\mathbb{1}\{\text{$server$ $n$ received at least one request}\}]$$ where $$\mathbb{1}\{\text{$server$ $n$ received at least one request}\}= \begin{cases} 1 \text{ if $server$ $n$ received at least one request},\\ 0 \text{ $otherwise$} \end{cases}$$

$$E[\mathbb{1}\{\text{$server$ $n$ received at least one request}\}] = P(\text{$server$ $n$ received at least one request})$$

$$P(\text{$server$ $n$ received at least one request})= 1 - e^{-\frac{10}{N}}$$

Therefore, in expectation:

$$E[S] = N(1 - e^{-\frac{10}{N}})$$

To check behavior at the boundary is as expected:

as $N$ approaches $\infty$, $E[S]$ approaches 0.

for $N = 1$, the problem reduces to finding the probability of $0$ requests.