1
$\begingroup$

In the Olympic format for sport climbing, eight athletes compete in three rounds of climbing. Their final score is the multiplication of their rankings in each round. For example, an athlete who comes 1st in the first round, 5th in the second round, and 7th in the third will have a final score of $1\times5\times7=35$. The athletes with the lowest final score wins.

Assuming that the competition is already partly underway (possibly even mid-round), is there a computer algorithm to quickly compute the probabilities $P_{ar}$ of each athlete $a$ achieving a final ranking $r$, assuming the performance of the athletes is entirely random from here on? Even with 8 athletes the brute force method seems too computationally intensive.

If this isn't computationally possible in a reasonable time, is there an algorithm to get "close enough" to those probabilities?

$\endgroup$
1
$\begingroup$

Brute force

If you want something easy to implement, brute force might be fast enough, assuming at least one round has been completed.

There are $8! = 40320$ possible permutations of the athletes, so in any round, there are 40320 possible rankings. Assuming the first round has been completed, there are only $40320^2 \approx 1.6 \times 10^9$ possible rankings for the next two rounds, all of them equally likely. A program should be able to enumerate all of them in a few seconds or minutes and compute the probability distribution of the final rankings for each athlete.

There are faster algorithms, and I will describe them below, but I'm unsure whether the time it takes to understand and implement them will outweigh the amount of CPU time they save.

Convolution

Let the random variables $X_1,X_2,X_3$ denote the athlete's ranking in the first, second, and third rounds. Then their final score will be $S = X_1 \times X_2 \times X_3$. Our strategy will be to compute the probability distribution for each $X_i$, then use that to compute the probability distribution for $S$.

Note that if a round has been completed, then the corresponding probability distribution is easy to compute: it assigns probability 1 to the rank the athlete actually obtained, and 0 to all others.

We can compute the probability distribution for a round that hasn't begun by enumerating all $8! = 40320$ possible permutations, observing the athlete's rank in each, and summing up how often each occurs. Or, more simply, we can note that since all permutations are equally likely, the distribution on the athlete's rank in this round is uniform, i.e., all possibilities have probability $1/8$.

We can compute the probability distribution for a round that has been partly completed by enumerating all $8! = 40320$ possible permutations, filtering out all of them that are incompatible with the results observed so far, then observing the athlete's rank in each that remains, and summing up how often each occurs.

So in this way we can obtain the probability distribution for $X_1$, $X_2$, and $X_3$. Now we obtain the probability distribution for $S$ from these distributions. In particular, the probability distribution for $T = X_1 \times X_2$ can be obtained as

$$\Pr[T=t] = \sum_{i=1}^8 \Pr[X_1 = i] \Pr[X_2 = t-i].$$

This requires 8 simple steps for each value of $t$, and there are $30$ possible values of $T$, so this can be done in $8 \times 30$ steps. Next, the probability distribution for $S = T \times X_3$ can be obtained in the same way. There are $80$ possible values of $S$, so this can be done in $8 \times 80$ steps.

The result is the probability distribution for $S$, the athlete's final score. This works with any number of unfinished rounds, even if one round is partly completed. The total running time is at most $40320 + 8 \times 30 + 8 \times 80$ simple steps, which is very fast; an implemention should complete the computation in millliseconds.

Related: Estimate distribution of a composite variable, largest samples of set of random variables, Polynomial Computation of the probability of a number of independent events.

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