Question
Let $n$ and $k$ be integers such that n is even, $n\ge2$ and $1\le k\le n$. You are having a party where $n$ students attended.
a) $k$ of these $n$ students are politically correct and, thus, refuse to say Merry Christmas.
Instead, they say Happy Holidays.b) $n – k$ of these $n$ students do not care about political correctness and, thus, they say Merry Christmas.
Consider a uniformly random permutation of these n students. The positions in this permutation are numbered as $1,2,…,n$.
Define the random variable $X$,
$X$ = the number of positions with $i$ with 1<=$i$<=$\frac{n}{2}$ such that both students at positions $i$ and $2i$ are politically correct.
What is the expected value $E(X)$ of the random variable $X$? (Use indicator variables)
Options:
a) $n$ $.$ $\frac{k(k-1)}{n(n-1)}$
b) $n$ $.$ $\frac{(k-1)(k-2)}{n(n-1)}$
c) $\frac{n}{2}$ $.$ $\frac{k(k-1)}{n(n-1)}$
d) $\frac{n}{2}$ $.$ $\frac{(k-1)(k-2)}{n(n-1)}$
I think the answer is c).
Attempt:
Indicator Variable:
$X$ $= 1$ if $i$ with 1<=$i$<=$\frac{n}{2}$ such that both students at positions $i$ and $2i$ are politically correct.
$X=0$ for all other cases
We need $E(X)$ = $\sum_{k=0}^{n/2} k . p(k)$
We have $\frac{n}{2}$ positions? but I can’t seem to find $p(k)$
There’s so much information given in this question that Im confused on how to break it down beyond the basic initial expected value steps.
Best Answer
This is pretty straightforward to solve using linearity of expectation. Let us set
$$ X_i = \mathbf{1}_{\{ \text{students at $i, \; 2i$ say ``Happy Holidays''\}}} $$
Then obviously $X = \sum_{i=1}^{n/2} X_i$, which gives you (by linearity of expectation)
$$ \mathbb{E}X = \mathbb{E}\left( \sum_i X_i \right) = \sum_i \mathbb{E}(X_i) = \frac{n}{2} \mathbb{E}(X_i), $$ since we have a uniformly random permutation. But, since $X_i$ are just indicator variables, we know that $\mathbb{E}(X_i) = \mathbb{P}(X_i = 1)$. You can calculate this probability yourself: it is the probability of positions $i, \; 2i$ having the same type of student. Denote by $A_i$ the event that student at position $i$ says "happy holidays". Then
$$ \mathbb{P}(X_i = 1) = \mathbb{P}(A_i \cap A_{2i}) = \mathbb{P}\left(A_i \ \middle|\ A_{2i}\right) \cdot \mathbb{P}(A_{2i}) = \frac{k-1}{n-1} \cdot \frac{k}{n}, $$ where $\frac{k}{n}$ occurs since we can choose $k$ out of $n$ students for position $2i$ and, when we condition on $A_{2i}$, we are left to choose $k-1$ students out of the remaining $n-1$.