4
$\begingroup$

I am currently working through Scornet2015 - Consistency of Random Forests.

I'm having trouble understanding a specific inequality that is used in the proofs without further explanation. I am assuming it is something rather general and not immediately related to the topic at hand.

As far as I can see, the inequality boils down to the following (I'll quote the full statements below).

$$ \mathbb{E}[X] \leq \xi + u \mathbb{P}[X > \xi] $$ where $u$ such that $X \leq u$. Why is that? I've looked at various basic tools such as Markov or Chebyshev inequalities as well as inequalities for tail probabilities but none seems to apply here.

First application

This considers (something like) the estimation error of a truncated estimate.

$$\begin{aligned} & \left.\mathbb{E}\left[\sup _{\substack{f \in \mathcal{F}_n(\Theta) \\ \|f\|_{\infty} \leq \beta_n}} \mid \frac{1}{a_n} \sum_{i=1}^{a_n}\left[f\left(\mathbf{X}_i\right)-Y_{i, L}\right]^2-\mathbb{E}\left[f(\mathbf{X})-Y_L\right]^2\right]\right] \\ & \quad \leq \xi+2\left(\beta_n+L\right)^2 \mathbb{P}\left[\sup _{\substack{f \in \mathcal{F}_n(\Theta) \\ \|f\|_{\infty} \leq \beta_n}}\left|\frac{1}{a_n} \sum_{i=1}^{a_n}\left[f\left(\mathbf{X}_i\right)-Y_{i, L}\right]^2-\mathbb{E}\left[f(\mathbf{X})-Y_L\right]^2\right|>\xi\right] \end{aligned} $$

Earlier, it is established that

$$\sup _{\substack{f \in \mathcal{F}_n(\Theta) \\\|f\|_{\infty} \leq \beta_n}}\left|\frac{1}{a_n} \sum_{i \in \mathcal{I}_{n, \Theta}}\left[f\left(\mathbf{X}_i\right)-Y_{i, L}\right]^2-\mathbb{E}\left[f(\mathbf{X})-Y_L\right]^2\right| \leq 2\left(\beta_n+L\right)^2$$

Second application

This considers the variation of the estimate $m$ in cells $A_{n}(\mathbf{X}, \Theta)$ of the random forest. The variation is defined as $\Delta(m, A)=\sup _{\mathbf{x}, \mathbf{x}^{\prime} \in A}\left|m(\mathbf{x})-m\left(\mathbf{x}^{\prime}\right)\right|$ and thus upper-bounded by the supremum norm $\|f\|_{\infty}:=\sup _{x \in[0,1]}|f(x)|$.

$$ \begin{aligned} \mathbb{E}\left[\Delta\left(m, A_n(\mathbf{X}, \Theta)\right)\right]^2 & \leq \xi^2+4\|m\|_{\infty}^2 \mathbb{P}\left[\Delta\left(m, A_n(\mathbf{X}, \Theta)\right)>\xi\right] \end{aligned} $$

$\endgroup$
2
  • 2
    $\begingroup$ In the applications you describe it is assumed that $X \lt u$, not that $\mathbb E[X] \lt u$. Deriving the inequality from there is straightforward $\endgroup$
    – J. Delaney
    Mar 22, 2023 at 10:45
  • $\begingroup$ Thank you for your comment, I have edited the question. $\endgroup$
    – ngmir
    Mar 22, 2023 at 12:32

1 Answer 1

1
$\begingroup$

Let $\Omega$ be the sample space and $X: \Omega \to \mathbb{R}$ a random variable. Assume $X < u$, i.e. $X(\omega) < u$ for all $\omega \in \Omega$.

Then

$$ \begin{align} \mathbb{E}[X] &= \sum_{\omega \in \Omega} \mathbb{P}(\omega) X(\omega) \\ &= \sum_{\substack{\omega \in \Omega \\ X(\omega) \leq \xi}} \mathbb{P}(\omega ) \underbrace{X(\omega)}_{\leq \xi} + \sum_{\substack{\omega \in \Omega \\ X(\omega) > \xi}} \mathbb{P}(\omega) \underbrace{X(\omega)}_{\leq u} \\ & \leq \xi ~ \underbrace{ \mathbb{P}(X \leq \xi) }_{\leq 1} + u ~ \mathbb{P}(X > \xi) \\ & \leq \xi + u ~\mathbb{P}(X > \xi) \end{align} $$

$\endgroup$
1
  • $\begingroup$ on a second thought, the first equality might not be completely correct, maybe you also have to sum over the range of $X$. $\endgroup$
    – ngmir
    Mar 31, 2023 at 8:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.