Expected Value for $n$ values

Question

I've been thinking about this for a while and I can't seem to figure it out. In a class, a teacher will call a student to answer a questions and the number of questions $n$ is equal to the number of students. A question is asked to one student at random. Using linearity of expectation, if there are $n$ students and $n$ questions, what is the expected number of students that don't get called?

I decided to try it out with $n=2$. Using $1$ = called, and $0$=not called, there are 4 possibilities $(11, 10, 01, 00)$. Then, we would have to multiply the probability with the value. Now, I am totally lost. There is a probability of $1/4$ is for $00$, and $1/4$ for both $01$ and $10$ each. Then is the expected value just $3/4$?

And how would I apply it to $n$ cases, instead of just $n=2$?

Answer 1

For each question, the probability that a given student doesn't get called is $\left(\frac{n-1}{n}\right)$. Therefore, after all $n$ questions, the probability that a given student doesn't get called is $\left(\frac{n-1}{n}\right)^n$ Thus, the expected value of the number of students that don't get called is $$ n\left(\frac{n-1}{n}\right)^n\sim\frac ne $$ That is, for large $n$, approximately $\frac1e=36.79\%$ of them don't get called.

Answer 2

The probability of any given student getting called on any of the $n$ questions is just $p=\frac{1}{n}$.

Use the PDF of the Binomial distribution to calculate the probability that any given student never gets called on. Let $X$ denote the total number of times that a given student has been called on after all $n$ questions have been asked. The probability that a given student is never called is

$P(X=k)=C_k^n p^k (1-p)^{n-k}$

$\Rightarrow P(X=0)=C_0^n p^0 (1-p)^{n}=(1-p)^n$ since $C_0^n=p^0=1$.

To get the expected number of students never called on, multiply this probability by the number of students in the class: $E=n(1-p)^n=n(1-\frac{1}{n})^n$.

Alternatively, you could say that the proportion of students never called on is

$\frac{E}{n}=(1-\frac{1}{n})^n$. For large $n$ you can calculate

$\lim\limits_{n \to \infty}(1-\frac{1}{n})^n=1/e\approx36.8\%$

Answer 3

Let's use explicitly the linearity of the expectation. We start defining, for $i=1,2,\ldots,n$,

$$ X_i = \left\{ \begin{array}{ll} 1 & i\text{-th student is not called}\\ 0 & i\text{-th student is called}\\ \end{array} \right. $$

As has been stated by previous answers, $$P(X_i=1) = \left(\frac{n-1}{n}\right)^n$$

because we assume that the professor makes $n$ independent calls and at each call the probability of a student not been chosen is $(n-1)/n$. Therefore,

$$E[X_i] = \left(\frac{n-1}{n}\right)^n,$$

and this holds for every student, that is for $i=1,2,\ldots,n$.

We can then define the number of not called students as

$$X = X_1 + X_2 + \cdots + X_n$$

And applying the linearity of the expectation we get

\begin{align} E[X] &= E[X_1]+E[X_2]+\cdots+E[X_n]\\ &= nE[X_1]\\ &= n\left(\frac{n-1}{n}\right)^n \end{align}

where in the second equality we have used the fact that $E[X_1] = E[X_2] = \cdots = E[X_n]$.