Permutation on $1,\dots,n$. Expected value of the number of people with a blocked sight.

74 Views Asked by At

Let $n\ge10$. $n$ people numbered $1$ to $n$ are standing in line, while the height of person $i$ is $i$. We'd say that the sight of person $i$ is blocked if there exists a $j$ such that $j>i$ which stands in front of it in line. Let $X$ be the number of persons that their sight is blocked.

What is the expected value and variance of X?

I'd appreciate any hint or direction.

1

There are 1 best solutions below

4
On

Let $X_i$ be a random variable which is $1$ if person $i$ has their sight blocked, for $1\le i \le n$. Notice that $$ X=X_1+X_2+\dots+X_n. $$ Using linearity of expectation, $EX=EX_1+EX_2+\dots+EX_n$, and each $EX_i$ is just the probability that person $i$'s sight is blocked.

For the variance, $$ \text{Var }X = \sum_i \text{Var }X_i + \sum_{i\neq j}\text{Cov}(X_i,X_j) $$ The first summation ranges from $i=1$ to $n$, while the second is over all ordered pairs $(i,j)$ with both $i,j$ in $\{1,2,\dots,n\}$ for which $i\neq j$. Be careful to include both $(i,j)$ and $(j,i)$!

Letting $E_i$ be the event that $i$'s vision is blocked, its not too hard to show $\text{Var }X_i=P(E_i)(1-P(E_i))$, while $\text{Cov}(X_i,X_j) = P(E_i\cap E_j)-P(E_i)P(E_j)$. Once you compute these probabilities, you have your answer.