# Expected Value and Random variables

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.

• Are you familiar with other ways of finding expectation? For example, linearity of expectation? – platty Nov 30 '18 at 1:05
• I'm not familiar with that way. – Toby Nov 30 '18 at 1:49
• That’s probably the cleanest way to tackle this one. How do you usually use indicator random variables to solve problems? – platty Nov 30 '18 at 2:04
• I'll have to look into the linearity of expectations. I typically solve them like what I did for this questions attempt. This question seems much more different than the ones I tackled previously – Toby Nov 30 '18 at 2:53
• Your method isn’t actually using the indicators you define. The fact that you are using indicators at all is a strong sign that you should be using linearity of expectation. – platty Nov 30 '18 at 2:54

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