Expected Value and Random variables

Question

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.

Answer 1

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$.

Answer 2

If one of the answer choices is correct, it must be c). Consider the case $k=n$. Then every student is politically correct and $X={\frac n2}$. Consider the case $k=1$. Then $X=0$, because there are no positions $i$ where politically correct students are in positions $i$ and $2i$. ($i\neq2i$ and only one student is politically correct.) Of the answer choices, only c) gives $X={\frac n2}$ when $k=n$ and $X=0$ when $k=1$.