Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$



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.

share|cite|improve this question
up vote 1 down vote accepted

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

share|cite|improve this answer
This helps a lot. Thank you. – Lok Oct 6 '12 at 20:40

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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