2
$\begingroup$

Cards numbered 1, 2, . . . , n are randomly distributed to players 1, 2, . . . , n. Whenever two players compare their numbers, the one with the higher one is declared the winner. Initially,players 1 and 2 compare their numbers; the winner then compares with player 3; and so on. Let X denote the number of times player 1 is a winner, and let Y = X + 1. Express the following quantities in terms of n.

$P[Y = i]$ and $P[Y\geq i]$ for $i = 1,..,n$

$E[Y]$

$Var[Y]$

I really have a hard time with problems such as these and would appreciate any tips on how to go about solving such questions. My initial intuition says that maybe a geometric or negetive binomial distribution is the way to go but I am not sure how to proceed.

Thank you for any help.

1 Answers 1

2

Hint: We have $Y\ge i$ iff card held by Player $1$ is $\gt$ the cards held by Players $2$ to $i-1$. Since all arrangements of the cards held by the first $i$ players are equally likely, this is just $\dfrac{1}{i}$.

From the general expression for $\Pr(Y\ge j)$ it should not be hard to find an expression for $\Pr(Y=i)$.

The rest should now be accessible.

Remark: If you calculate $E(Y)$ the "normal" way, things will collapse in an interesting way. This is related to a useful general fact about how (for non-negative random variables) $E(W)$ is related to the tail function $\Pr(W\ge w)$.

  • 0
    This helps a lot. Thank you.2012-10-06