3
$\begingroup$

The well known result, $\mathbb{E}[\text{min} \{X_i \}_{i=1}^n ] = \frac{1}{n+1}$ and $\mathbb{E}[\text{max} \{X_i \}_{i=1}^n ] = \frac{n}{n+1}$ where $X_i$ are I.I.D Uniform$(0,1)$ random variables is a lifesaver. It can be extrapolated to find the expected minimum and maximum of $n$ Uniform$(a,b)$ variables.

I tried to use it in the discrete case. For example, consider the maximum of $10$ rolls of a $100$ sided die, the quick formula gives: $ \frac{10}{11}\cdot 100 = 90\frac{1}{11} \approx 90.91$. The true answer however is $91.4007585757 $ (using tail sum formula : $100 - \sum\limits_{i=1}^{99}(\frac{i}{100})^{10}$ )

Notice the approximation gives an underestimate.

Now consider using it to approximate the expected minimum.

$\frac{1}{11}\cdot 100 = 9\frac{1}{11} \approx 9.09$. The true answer however is $9.59924142434$ and again this formula under-approximates?

Why does this happen in both cases? Is there a cheeky way to tweek it for the discrete case to get a bit more accurate?

Thanks!

A little thing I have noticed that might help is the following:

The approximate min + approximate max is always $n$. However, by symmetry the true min + true max is always $n+1$. (because they are centred around the mean of $\frac{n+1}{2}$

$\endgroup$
1
  • $\begingroup$ Decent question, a very underappreciated consequence of the way you approximate continuous by discrete. Technically speaking, the second part hasn't been answered yet, so I'm looking forward to someone addressing that as well. $\endgroup$ Sep 20 at 6:05
2
$\begingroup$

Note that for $X$ positive we have $\mathbb EX=\int_0^\infty 1-F(x)\,\mathrm d x$. Now note that if $X$ is the discrete variant and $Y$ is the continuous approximation. Then $F_X\leq F_Y$ (as $F_X(x)=F_Y(x)$ for $1\leq x\leq 100$ and $F_Y$ is linear while $F_X$ is constant on $[x,x+1)$.).

Thus this also holds true for the distribution of max and min, and thus by above formula the expected values for $Y$ are smaller than those for $X$.

$\endgroup$
2
$\begingroup$

It under-approximates because you are approximating a random variable taking values in $$ \left\{\frac{1}{k},\frac{2}{k},\dots,\frac{k-1}{k}, 1\right\} $$ by a uniform random variable, that is, uniform on $$ \left(0,\frac{1}{k}\right] \cup \left(\frac{1}{k}, \frac{2}{k}\right]\cup \dots\cup \left(\frac{k-1}{k}, 1\right]\,. $$ Viewed differently, you replace the value $$ \frac{i}{k} $$ (for $1\leq i\leq k$) by a uniformly random value in $$ \left(\frac{i-1}{k}, \frac{i}{k}\right] $$ which leads to a (small) under-approximation.

$\endgroup$
5
  • $\begingroup$ As a corollary, a (first-order, not perfect, but closer) fix is to add $\frac{1}{2k}$ to the result, to make up for the shift and "re-center" your approximation. Since you multiply by $k$ in the end, that means adding $0.5$ to your estimates. In your example, that'll give 91.41 and 9.59. $\endgroup$
    – Clement C.
    Sep 19 at 21:20
  • 1
    $\begingroup$ Super answer clement! Thank you very much. $\endgroup$ Sep 19 at 22:35
  • $\begingroup$ @BearCakes100 Glad this helped! $\endgroup$
    – Clement C.
    Sep 19 at 22:43
  • 1
    $\begingroup$ I have noticed a typo in your answer. I think you mean: $\left(0,\frac{1}{k}\right] \cup \left(\frac{1}{k}, \frac{2}{k}\right]\cup \dots\cup \left(\frac{k-1}{k}, 1\right]\,.$ @Clement C. $\endgroup$ Sep 20 at 8:40
  • 1
    $\begingroup$ @BearCakes100 Indeed, good catch. I just cannot count. $\endgroup$
    – Clement C.
    Sep 20 at 9:39

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.