• Five distinct numbers are randomly distributed to players numbered $1$ through $5$.
  • 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 her number with that of player $3$, and so on.

Let $X$ denote the number of times player $1$ is a winner. Find $P\left\{X = i\right\}\,,\ i = 0, 1, 2, 3, 4$.

I've successfully come up with a formula to solve this by recognizing it from the answers that I've computed independently. Given a well-ordered set of $N$ unique and distinct numbers mapped onto a set of natural numbers from $1$ to $N$...

$$ P\left\{\mathbb{X}=n\right\} = {1 \over N}\sum_{k = 1}^{N}{\left\{\prod_{i = N - n}^{N - 1} \left[1 - {\binom{N-k}{1} \over{i \choose 1}}\right]\right\} {{N - k \choose 1} \over {N - n - 1 \choose1}}} $$

But it doesn't seem clear to me why this works... I feel like there should be an elegant solution to this problem such as the formula above but even though it satisfies my answers, there is a few problems with it, the first being that the product term can produce negative probabilities (although this doesn't matter in the end as it is canceled out by other product term iterations that are 0).

The way I got it was by first recognizing that the total probability of $P\left\{\mathbb{X}=i\right\}$ is going to be equal to the sum of all the possibilities of $k$ being chosen for the first player each multiplied/intersected with the probabilities for the conditions of the next moves that would satisfy the subject condition for that specific value chosen for $k$.

I feel like there is a distribution or some sort of function that already models this, but I haven't been taught it yet or I'm missing something.

Edit: Here's a picture of $P\left(\mathbb{X} = 3\right)$ :


Notice the negative product terms and the appearance of 0 in the product terms, making entire sum terms null. Meanwhile, the binomial terms are required for the $\binom{0}{1}$ case. I feel like there's something wrong with the formula because it's hitting too many edge cases with the operators.

One thing that isn't noticeable in the picture is that $P\left(player\ 1 = k\right)$, which is always $\frac{1}{N}$.

  • $\begingroup$ Not sure I follow your formula. For $n=1$, isn't the product negative? It just has one term...$\left(1-\frac 54\right)$. $\endgroup$ – lulu Sep 25 '16 at 10:27
  • $\begingroup$ @lulu Ah, I thought I made a mistake. I changed the product term to have $5-k$ $\endgroup$ – CinchBlue Sep 25 '16 at 10:31
  • $\begingroup$ I am posting a solution below... $\endgroup$ – lulu Sep 25 '16 at 10:32

Let's say the five assigned numbers were $\{a,b,c,d,e\}$

How can player $1$ have zero victories? Well, we just need $a<b$. But, as we either have $a<b$ or $b>a$ with equal probability we see $P(X=0)=\boxed {\frac 12}$.

This line of reasoning works for $n=1,2,3$. For any of those, we consider the first $n+2$ numbers in the list. We need the greatest to be in the last slot (probability $\frac 1{n+2}$) and the second greatest to then be in the first slot (conditional probability $\frac 1{n+1}$). Thus for these $n$ we get probability $P(x=n)=\boxed {\frac 1{(n+2)(n+1)}}$

For $n=4$ we simply need that the greatest be in the first slot, so $P(X=4)=\boxed {\frac 15}$

Sanity Check: We should confirm that these add to $1$. But we see that $$\frac 12+\frac 16+ \frac 1{12}+\frac 1{20}+\frac 15=1$$

  • $\begingroup$ The list is $\{a,b,c,d,e\}$, the assigned numbers. If, say, $n=2$ then we need $a>b$, $a>c$, $a<d$. Thus $d$ must be the greatest of the first four, and $a$ must be the second greatest. $\endgroup$ – lulu Sep 25 '16 at 10:48
  • $\begingroup$ The answer given doesn't actually answer my question though. I do agree that this is a much simpler way of doing this, but it doesn't explain why the formula I have written works. $\endgroup$ – CinchBlue Sep 25 '16 at 10:49
  • $\begingroup$ I found your formula very hard to parse. First version was simply wrong. Can you confirm that the numbers match? $\endgroup$ – lulu Sep 25 '16 at 10:50
  • $\begingroup$ What would your formula be for $N$ players? Clearly, there's nothing special about $5$. If the formula is specific to $5$...well, there's lots of functions that match a finite list of values. $\endgroup$ – lulu Sep 25 '16 at 10:53
  • $\begingroup$ To be precise: let's take $n=0$. Now, you present me with $\prod_{i=5}^4 (***)$. How should I interpret that? $\endgroup$ – lulu Sep 25 '16 at 10:56

My original answer, appended below, is correct but does not reveal the simple end result obtained by @lulu. The latter can be paraphrased as follows: Player $P_1$ survives at least $r\geq0$ matches iff $N_1=\max\{N_1, N_2,\ldots, N_{r+1}\}$. The probability that this is the case is ${1\over r+1}$, by symmetry. It follows that $$P[X=r]={1\over r+1}-{1\over r+2}={1\over(r+1)(r+2)}\ .$$

Original answer: Assume that the numbers $1$, $2$, $\ldots$, $n$ are randomly distributed to the players $P_i$ $(1\leq i\leq n)$. If the first player $P_1$ has received the number $k\in[n]$ then among the players $P_2$, $\ldots$, $P_n$ there are $k-1$ "white balls" for him and $n-k$ "black balls". The probability $p_k(r)$ that this first player survives $r$ fights is the probability that his first $r$ drawings result each in a white ball, and computes to $$p_k(r)={k-1\over n-1}\ {k-2\over n-2}\ \cdots\ {k-r\over n-r}\quad(0\leq r< k),\qquad p_r=0\quad(r\geq k)\ .$$ The probability that the $r^{\rm th}$ victory is his last is then given by $p_k(r)-p_k(r+1)$.

Note that $P_1$ received each $k\in[n]$ with equal probability ${1\over n}$. The probability that the random variable $X$ defined in the question has a given value $r\in[0\>..\>n-1]$ is therefore $$P[X=r]={1\over n}\sum_{k=1}^n\bigl(p_k(r)-p_k(r+1)\bigr)\ .$$


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.