Riddler Solution: Can You Skillfully Ski The Slopes?

Introduction

In Zach Wissner-Gross’s Fiddler on the Proof, he mentions the following problem from nearly five years ago, when it was still FiveThirtyEight’s The Riddler:

← Previous

Introduction

In Zach Wissner-Gross’s Fiddler on the Proof, he mentions the following problem from nearly five years ago, when it was still FiveThirtyEight’s The Riddler:

You are one of $n=2$ finalists in a skiing championship. There are two rounds: in the first round, each finalist skis down the mountain, recording their finishing time; this is repeated in the second round, with the least *total *time for both runs winning the championship. This is the top talent in the world, so the time for every run is independent and identically distributed. Having learned that you have the best time in the first round, what is the probability that you will win the championship? For extra credit, what if $n=30$ ?

In the original problem, the finishing times were normally distributed. The neat feature of this problem is a cocktail-napkin solution for $n=2$ that does not depend on this distribution. However, the extra credit for larger $n$ — for normally distributed run times– appears to require resorting to simulation or approximation, although Josh Silverman provides some really interesting recent asymptotic analysis.

The motivation for this post is to capture my notes on the exact solution for any $n$ for the case where finishing times are *uniformly *distributed. (This feels to me like a slightly more natural version of the problem, without the unrealistic negative tails.)

Solution

Define random variables $X$ and $Y$ to be the finishing times for our first and second run, respectively, and similarly define $R_i$ and $S_i$ to be the first and second round times for each competitor $i \in {1,2,\ldots,n-1}$ . Define event $A_i$ to be $X+Y<R_i+S_i$ (i.e., we beat competitor $i$ overall) and event $B_i$ to be $X<R_i$ (i.e., we beat competitor $i$ in the first round). Then we want to compute the probability

$P(\bigcap\limits_{i=1}{n-1}A_i | \bigcap\limits_{i=1}{n-1}B_i)$

Applying Bayes’ theorem, and re-ordering and re-grouping the intersection of events in the numerator, we have

$\frac{P(\bigcap\limits_{i=1}{n-1}A_i \cap B_i)}{P(\bigcap\limits_{i=1}{n-1}B_i)}$

There are two key observations: first, by symmetry, the probability in the denominator– that we are the leader after the first round– is $1/n$ . Second, in the numerator, if we condition on fixed times for our two runs, say for example $X=x=0.3$ and $Y=y=0.8$ , then the $n-1$ events $A_i \cap B_i$ are independent– so we can multiply them– and they all have the same probability.

The following figure shows this example situation, where the area of the shaded region is the probability $P(A_i \cap B_i)=P(x+y<R_i+S_i \land x<R_i)$ that we beat a particular competitor in both rounds.

This shaded region has two different shapes depending on whether $x+y$ is less than or greater than 1; putting everything together, the desired probability is

$n \int_{x=0}1(\int_{y=0}{1-x}(1-x-\frac{1}{2}y^2)^{n-1}\mathrm{d}y + \int_{y=1-x}^1((1-x)(1-y)+\frac{1}{2}(1-x)2){n-1}\mathrm{d}y)\mathrm{d}x$

Applying binomial expansion to the powers and moving the integrals inside the resulting summation gives the following formula:

$n\sum\limits_{k=0}^{n-1}{n-1 \choose k}\frac{1}{2^k}(\frac{(-1)^k}{(2k+1)(n+1+k)}+\frac{(n-1-k)!(n-1+k)!}{(2n)!})$

The figure below shows this probability vs. the number of skiers $n$ .

For 5 or 6 skiers, it’s roughly a coin toss whether you retain your first-round lead. When $n=30$ , the probability is about 0.226.

Post navigation

Post navigation

Similar Posts