Does the sample minimum of $Y_i=h(X_i)$, $X_i\sim$ uniform, converge to $\min_x h(x)$?

Question

Let $h:[a,b]\to \mathbb{R}$ be Borel and continuous. So there exists $x^*$ such that $\min_{x\in[a,b]} h(x) = h(x^*)$. For simplicity assume $x^*$ is unique. Let $X_1,\dotsc, X_n$ be IID $\mathcal{U}(a,b)$ RVs and let $Y_i = h(X_i)$ for $i=1,2,\dotsc, n$. Let $Y_{(1)}=\min \{Y_1,\dotsc, Y_n\}$. Since this depends on $n$, we may want to write $Y_{(1)}^{(n)}$ instead.

My question Does $Y_{(1)}^{(n)}\to h(x^*)$ as $n\to \infty$ (in any sense: in probability, almost surely, in mean etc)?

My attempt: By continuity, for $\epsilon>0$ there exists a $\delta>0$ such that $|x-x^*|<\delta$ implies $|h(x)-h(x^*)|< \epsilon$. Conditional on $Y_{(1)}=Y_j=h(X_j)$, we have $$\{|X_j-x^*| < \delta\}\subset \{|h(X_j)-h(x^*)|<\epsilon\},$$ from which it follows that $$\mathbb{P}(|Y_{(1)}-h(x^*)|<\epsilon) \geq \frac{2\delta }{b-a}.$$ but this seems like a dead end.

Intuitively, I feel like it is true and some numerical experiments support it: The exact minimum value of $f(x)=x^2-1-x$ is $-1.25$ and the sample minimum of uniform $x_i$ in $[0,1]$ mapped up to $y_i=f(x_i)$ is $-1.249963$--with seed 17.

Any other ideas or possibly counterexamples? If it is true, can it be generalized to $K\subset \mathbb{R}^d$, compact with finite measure such that a uniform distribution is well-defined on $K$, and $h:K\to \mathbb{R}$?

Answer 1

It is true, and it holds almost surely. To save characters, I'm going to put $Y_{(1)}^{(n)} = Y_n$. Put $h: K \to \mathbb R$ a continuous function on a compact set $K$. Let $\mu$ be the uniform probability measure on $K$, and $x^*$ where $h$ attains its minimum. We will also need that $\mu(\{ x \mid |x - x^*| < \delta\}) > 0$ for all $\delta$; certainly this is the case if $K$ is an interval.

Fix any $\epsilon > 0$; we will show via Borel-Cantelli that the event $|Y_n - h(x^*)| \geq \epsilon$ happens only finitely many times with full probability. By continuity, there is some $\delta$ such that if $x \in K$ and $|x - x^*| < \delta$, $|h(x) - h(x^*)| < \epsilon$. Then, $$|Y_n - h(x^*)| \geq \epsilon \iff |X_i - x^*| \geq \delta$$ for all $i = 1, \dots, n$. But $$\mu(\{ x \mid |x - x^*| < \delta\}) > 0$$ by assumption and so $$P(|X_i - x^*| \geq \delta) < 1.$$ Abbreviate this probability to $p$. Then, $$\sum_{k=1}^\infty P(|Y_k - h(x^*)| \geq \epsilon) = \sum_{k=1}^\infty p^k < \infty$$ so Borel-Cantelli yields that with probability one, eventually $|Y_k - h(x^*)| < \epsilon$. Since this holds for arbitrary $\epsilon > 0$, we must have $Y_n \to h(x^*)$ almost surely.

Answer 2

By definition the CDF of $Y_{(1)}$ is given by $$\Pr(Y_{(1)}\le t) = 1-\prod_{i=1}^n(1-\Pr(Y_i\le t)) = 1-\prod_{i=1}^n(1-\Pr(X_i\in h^{-1}(-\infty,t] )) = 1-(1-a(t))^n$$

Where $a(t):=\Pr(X_i\in h^{-1}(-\infty,t])\in[0,1]$ does not depend on $i$ by the i.i.d. assumption.

So now the convergence of the CDF depends on the behaviour of $a$ (which itself depends on $h$) but note that :

• $a$ is non-decreasing
• if we denote by $h_+$ (resp. $h_-$) the supremum (resp. infimum) of $h$ over $[a,b]$, we have $a(h_+) =1$ and $a(h_-)=0$ (note that with your notation, $h_-\!\equiv h(x^*)$).

If you can furthermore check/assume that $a(t)>0$ for all $t>h_-$, then you can conclude that the CDF of $Y_{(1)}$ converges pointwise to $$F(t) := \begin{cases} 0, &\text{if } t\le h(x^*),\\ 1,\! &\text{if } t>h(x^*) \end{cases} $$ That is, $Y_{(1)}$ converges in distribution (and thus, in probability) to $h(x^*)$. I believe the multi-dimensional case can be handled similarly.