1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Are you familiar with other ways of finding expectation? For example, linearity of expectation? $\endgroup$ – platty Nov 30 '18 at 1:05
  • $\begingroup$ I'm not familiar with that way. $\endgroup$ – Toby Nov 30 '18 at 1:49
  • $\begingroup$ That’s probably the cleanest way to tackle this one. How do you usually use indicator random variables to solve problems? $\endgroup$ – platty Nov 30 '18 at 2:04
  • $\begingroup$ 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 $\endgroup$ – Toby Nov 30 '18 at 2:53
  • 1
    $\begingroup$ 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. $\endgroup$ – platty Nov 30 '18 at 2:54
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.