Questions tagged [empirical-processes]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
0 answers
26 views

Do we need to assume that $y$ is bounded

Suppose that $X_1,\dots, X_n$ are iid $P$ on $\mathcal{X}$. The empirical measure $\mathbb{P}_n$ is defined by $$\mathbb{P}_n:=\frac{1}{n}\sum_{i=1}^n\delta_{X_i}$$ For a real-valued function $f$ on $\...
Hermi's user avatar
  • 1,506
1 vote
0 answers
18 views

How to prove that every Donsker class is also a Glivenko-Cantelli class

From https://en.wikipedia.org/wiki/Vapnik–Chervonenkis_theory Let $X_1, ..., X_n$ be a random sample from a probability distribution P. Let $$P_nf=\frac{1}{n}\sum_{i=1}^nf(X_i), \quad Pf=\int fdP.$$ A ...
jsmath's user avatar
  • 421
0 votes
0 answers
35 views

Prove Glivenko-Cantelli (GC) by bracketing

Question: My question about the theorem Glivenko-Cantelli (GC) by bracketing is: if $N_{[]}(\varepsilon,\mathcal{F},L_{1}(P))=\infty$, which part of the above proof will fail, thus GC will fail. ...
Hagan Ross's user avatar
0 votes
0 answers
54 views

The asymptotic distribution of the criterion function in M-estimation

Suppose that we are interested in a parameter (or functional) $\theta$ attached to the distribution of observations $\left\{ X_{1},\ldots,X_{n}\right\} $. A popular method for finding an estimator $\...
Hagan Ross's user avatar
0 votes
0 answers
42 views

Bracketing entropy for unimodal functions

This is exercise 2.3 from van de Geer's Empirical processes in M-estimation. Let $\mathcal G$ be the class of unimodal functions $g : \mathbb R \rightarrow [0, 1]$. A function $f$ is unimodal if there ...
dmh's user avatar
  • 2,938
0 votes
0 answers
21 views

Joint measurability of discrete integral.

I'm currently considering the following map: Let $\mathcal{F}$ be a subset of some $L^2$ space with respect to a probability measure on $\mathbb{R}$ and let $X=(X_1,X_2,\ldots,X_n)$ be points on the ...
Milos Mathias Koch's user avatar
2 votes
0 answers
51 views

Translation of box type ball to center it in a convex set but maintaining the covering properties

I have the following problem. Suppose to have a cube $Q$ and a symmetric box type ball $B$ whose center is outside Q, but such that $Q\cap B \ne\emptyset$. Furthermore $B$ is not oriented like $Q$. I ...
Giorgio's user avatar
  • 21
1 vote
0 answers
26 views

Does the empirical c.d.f. converge to the population c.d.f. when the data is drawn from a mixing stochastic process

For i.i.d. observations, the Dvoretzky–Kiefer–Wolfowitz inequality tells us that the empirical c.d.f. almost surely converges to the population c.d.f. (i.e., $\underset{x \in \mathbb{R}}{\sup} | F_n(x)...
ZouX's user avatar
  • 11
0 votes
0 answers
31 views

Controlling the distance between two quantile functions of discrete distributions

Let $(X_i)_{1\leq i \leq n}$ and $(Y_i)_{1\leq i \leq n}$ be i.i.d. samples of two different distributions. Then, define the "weighted empirical cumulative distributions functions" $F_{n,Y}(...
Skywear's user avatar
  • 184
1 vote
0 answers
54 views

distance between the uniform empirical process and time-rescaled uniform quantile process always less than $n^{-1/2}$

First give some notation and definitions: Let $U_1,\dots,U_n$ be iid $Uniform[0,1]$ distributied and let $0=U_{0,n}\leq U_{1,n}\leq\cdots\leq U_{n,n}\leq U_{n+1,n}=1$ be their order statistics. For $t\...
allen i's user avatar
  • 301
-1 votes
1 answer
48 views

3D Surface Fitting to a Empirical Dataset

I have a large empirical dataset which may be modelled via the following 3D surface formula: A*[X]+B*[Y]+C*[Z]+D*[X]*[Z] = 1 Where X & Z are the independent ...
Admirable-Sun-1263's user avatar
1 vote
0 answers
55 views

"$\ell^\infty(T)$ is separable if and only if $T$ is countable" -- this is not correct, is it?

I am reading these notes https://mkosorok.web.unc.edu/wp-content/uploads/sites/14747/2017/07/lecture06.pdf on empirical processes. I am confused by the statement on slide 38: Note that $\ell^\infty(T)...
Syd Amerikaner's user avatar
3 votes
0 answers
31 views

Does the distribution of the maximum increase when adding independent Gaussian processes?

Let $x(t)$ and $y(t)$ be independent, mean-zero Gaussian processes, indexed over some general metric space $T$. Is it true that $\Pr(\sup_{t \in T} |x(t) + y(t)| > z) \ge \Pr(\sup_{t \in T} |x(t)| &...
Rob's user avatar
  • 401
1 vote
1 answer
108 views

The covariance of a multivariate Empirical Process

Van der Vaart states in his book "Asymptotic Statistics" that an empirical process (of the sample $X_1, X_2, \dots, X_n$) is defined by $$G_n = \sqrt n( P_n - P),$$ where $P$ is the true ...
lmaosome's user avatar
  • 632
2 votes
0 answers
39 views

Maximal inequality regarding the empirical distribution function

Let $F$ be a distribution function and $F_n$ the corresponding empirical distribution function. By the empirical process theory, we have the following stochastic equicontinuity condition : for some ...
WaitedLeastSquare's user avatar
1 vote
0 answers
33 views

How to calculate the unifrom entropy or VC dimension of the following class of functions?

When dealing with U process I meet with such a uniform entropy to calculate. For any $\eta>0$, function class $\mathcal{F}$ containing functions $f=\left(f_{i, j}\right)_{1 \leq i \neq j \leq n}: \...
leslie zhang's user avatar
2 votes
0 answers
239 views

Multivariate Donsker Theorem

Suppose that $(\Omega,\mathcal F, P)$ is a probability space, and let $Z = (X,Y)$ be a $\mathbb R^2$-valued random variable. Let $F_X$ and $F_Y$ denote the respective marginal distribution function of ...
Syd Amerikaner's user avatar
4 votes
2 answers
262 views

Union Bound of two events?

I am trying to understand the assumption proof of Theorem 2(Page -$7$) in the paper "A Universal Law of Robustness via isoperimetry" by Bubeck and Sellke. Inequality 1 \begin{align} \mathbb{...
user avatar
4 votes
1 answer
118 views

Convergence of non iid observations on the empirical distribution

Let $f$ be a function on domain $X$ with binary output $f: X\to \{0,1\}$. We define an arbiatry distribution $\mathcal{Q}$ over $X$ and the empircal distribution of $n$ samples from $\mathcal{Q}$ -- $\...
user2757771's user avatar
0 votes
1 answer
53 views

Is this sub-Gaussian random variable?

Say $X_1, X_2$ are i.i.d. sub-Gaussian variables following the definition in High-Dimensional Probability. Denote $X = (X_1, X_2)^T$, and $\eta$ is some positive constant. Is the following random ...
Hepdrey's user avatar
  • 73
3 votes
0 answers
118 views

Convergence of estimator defined by supremum over measurable sets

Let $X \in L_1$ be a positive random variable on the probability space $([0,1], \mathcal B, P)$, where $\mathcal B$ is the Borel $\sigma$ algebra on $[0,1]$. Consider $$\phi(A) = E[X\mid A] \cdot I\...
northwiz's user avatar
  • 325
0 votes
1 answer
81 views

How to understand random probability measure in context of concrete example?

I was reading materials about empirical distribution, on Wikipedia, it says empirical distribution is an example of empirical measure. On the page of empirical measure, it says the empirical measure ...
JoZ's user avatar
  • 935
2 votes
0 answers
117 views

A generalization of the KMT theorem for empirical processes

Recall the KMT embedding for empirical processes: For all $n\geq 1$, there exists a probability space with $(U_k)_{1\leq k\leq n}$ i.i.d with uniform $[0, 1]$ distribution and $W_0$ a Brownian bridge ...
Papagon's user avatar
  • 305
1 vote
2 answers
267 views

Discrete version of Dudley's inequalilty: Assuming set is finite wlog?

I'm self-studying Vershynin's High-dimensional probability book. I have a question about the proof of Theorem 8.1.4: Let $(X_t)_{t\in T}$ be a mean-zero random process on a metric space $(T,d)$, with ...
Idontgetit's user avatar
  • 1,351
0 votes
1 answer
68 views

Bounding an integral involving tail probabilities

I am currently reading through Van der Vaart and Wellner's book on empirical process theory. In chapter 2.9, they define the quantity $$||\xi||_{2,1} \equiv \int_0^\infty \sqrt{P(|\xi| > x)}\,\...
stats_model's user avatar
  • 1,061
2 votes
1 answer
132 views

Concentration of empirical measure under Prokhorov distance

For any two probability measures $\mu,\nu$ over $\mathbb{R}^d$, the Prokhorov distance is defined to be $$d_P(\mu,\nu)=\inf\{\epsilon:\mu(A)\le \nu(A^{\epsilon})+\epsilon\text{ and }\nu(A)\le\mu(A^{\...
Paul's user avatar
  • 475
9 votes
0 answers
236 views

$P(X_{(n-k_n)}>X_1\mid X_1>u_n)=0$?

Let $X_1,X_2,\dots$ be continuous random variables with full support (I need the result when they follow AR time series $X_i=\alpha X_{i-1}+\varepsilon_i$ for iid epsilons. But if you will consider ...
Albert Paradek's user avatar
1 vote
0 answers
174 views

What is a Kolmogorov inequality, and why?

I encountered a problem while reading a classic paper. The random variable $V \sim exp(1)$, $(v_{(1)},v_{(2)},...,v_{(n)})$ are ordered. The paper said, for any $\epsilon$, based on the Kolmogorov ...
Happy Superman's user avatar
1 vote
0 answers
39 views

Does $E[\hat{F}_n(X_1) - F(X_1) \mid \cdots]\to 0$?

Let $\binom{X_1}{Y_1}, \binom{X_2}{Y_2} \dots $ be iid vectors. Denote $\hat{F}^x_n(\cdot) = \frac{1}{n}\sum_{i=1}^n1[X_i\leq \cdot]$ an empirical distribution function of $X$, and similarly $\hat{F}^...
Albert Paradek's user avatar
2 votes
1 answer
106 views

Bounding the uniform deviation of the empirical risk from the risk over a finite function class.

I am having difficulty interpreting the following theorem from here as a probability statement: Theorem. For all $\delta$ such that $0 < \delta < 1/2$, with proability at least $1 - \delta$ the ...
microhaus's user avatar
  • 892
6 votes
1 answer
170 views

Does the law of large numbers hold for covering numbers?

I am self-studying empirical process theory. I have encountered the covering number $N(\delta,\mathcal{G},P)$, as well as the empirical version $N(\delta,\mathcal{G},P_n)$. It seems intuitive to ...
Idontgetit's user avatar
  • 1,351
1 vote
1 answer
67 views

Lower-bound on $\mathbb E[\|A^{-1}x\|]$ when $A$ is a positive-definite matrix with eigenvalues in $[a,b]$ and $x=(x_1,\ldots,x_n)$ is iid Rademacher

Let $A$ a positive-definite $n \times n$ matrix with eigenvalues in the interval $[a, b]$ and let $x=(x_1,\ldots,x_n)$ be a random vector with iid components distributed uniformly in $\{\pm 1\}$. ...
dohmatob's user avatar
  • 9,410
1 vote
0 answers
54 views

Proof check: Concentration of maximum of a certain empirical process

Let $x_1,\ldots,x_n$ be iid uniformly distributed on the unit-sphere in $\mathbb R^d$ and let $y_1,\ldots,y_n$ be iid uniformly distributed on $\{\pm 1\}$, and independent of the $x_i$'s. Define $Z_n:=...
dohmatob's user avatar
  • 9,410
0 votes
0 answers
31 views

Large Deviation Principle for the Empirical Path Law. Brownian Particles.

I'm looking for a Large Deviation Principle for the Empirical Path Law. Someone must have done this right? That is, for $i\in \mathbb{N}$, $t\in[0,T]$, let $X^i(t)\in \mathbb{R}^d$ be (the position of)...
Monty's user avatar
  • 2,180
1 vote
0 answers
87 views

Empirical Risk minimization, symmetrization lemma

I have a question related to obtaining uniformly good estimates of error for the class of hypothesis function. The following images are taken from the paper: "The Complexity of Learning According ...
Gantavya Bhatt's user avatar
2 votes
2 answers
305 views

Bracketing numbers for products of functions from two spaces

I am reading materials related to empirical processes. The statement below is about measuring the complexity of function classes using bracketing numbers. I wonder if the inequality therein for ...
OwlMetrics's user avatar
3 votes
2 answers
2k views

Brownian motion: law of iterated logarithm

I am doing a homework question. But I get confused. $\{B_t: t \geqslant 0\}$ is a standard Brownian motion. Show that there exists $t_{1}<t_{2}<\cdots$ with $t_{n} \rightarrow \infty$ such that ...
PaulWH's user avatar
  • 312
1 vote
1 answer
153 views

How to generate the pairwise win probability matrix according to the win probability of each competitor?

For example, I have the win probability vector p = [0.2, 0.5, 0.8] which means the first player wins with a probability of 0.2 against a random player, the player 2 ...
hayj's user avatar
  • 123
0 votes
1 answer
116 views

Identical CDF over sets of measure zero.

I have seen many variations of this statement in different texts. $\bullet$ "Two densities with the same cumulative distribution function are equal except on a set of Lebesgue measure zero." ...
Short and Fuzzy's user avatar
1 vote
0 answers
30 views

What is known about convergence of empirical extrema?

VC theory provides an answer to Problem 1 specified below. I am wondering what is known about a similar issue, Problem 2. $$ ~ $$ Problem 1 Let $X$ be a set, let $\mathcal{D}$ be a distribution over $...
π314's user avatar
  • 133
3 votes
0 answers
230 views

Uniform almost sure convergence of the partial sum process

Suppose $X_i$, $i=1,2,...$, are iid random variables with $EX_i=0$ and $EX_i^2 < \infty$. For each $x \in (0,1)$, $\frac{1}{\lfloor n x \rfloor} \sum_{i=1}^{\lfloor n x \rfloor} X_i \stackrel{a.s....
LostStatistician18's user avatar
3 votes
0 answers
172 views

When does almost sure pointwise convergnce of a sequence of stochastic processes imply uniform almost sure convergence

Suppose $\{X_n(t) \; : \; t \in K\}$ $n=1,2,...$ is a sequence of stochastic processes indexed by a compact subset of a metric space $K$, and $\{X_\infty(t) \; : \; t\in K\}$ is a limiting process ...
LostStatistician18's user avatar
4 votes
1 answer
426 views

How to fit ordinary differential equations to empirical data?

For some biological systems, there exists ordinary or partial differential equations that allow one to simulate their activity/behavior over time. Some of these models even produce data that is very ...
mmh's user avatar
  • 237
1 vote
1 answer
45 views

Examples of distributions with small $\ell_\infty$ norm?

Let $X \sim \mathcal{N}(0, I_{n \times n})$, so that $X$ is, in distribution, $n$ independent and identically distributed draws of a $\mathcal{N}(0, 1)$ random variable. Then it is well known that $$...
Drew Brady's user avatar
  • 3,174
2 votes
0 answers
509 views

Bracketing number for monotone functions $f:\mathbb{R} \to [0,1]$.

I have been trying to understand a bound on the log of the bracketing number for monotone functions with range in $[0,1]$. My book claims that constructing the brackets as piecewise constant functions ...
JohnK's user avatar
  • 6,392
2 votes
1 answer
676 views

Almost sure strong convergence of the empirical distribution

Let $X_1,X_2,\ldots$ be a sequence of independent and identically distributed real-valued random variables, each defined on the probability space $(\Omega,\mathcal{F},P)$ and with distribution $Q(\...
a.arfe's user avatar
  • 197
1 vote
2 answers
97 views

Understanding how to do an Empirical Mode Decomposition

I am trying to create my own code for Empirical Mode Decomposition and extraction of IMFs. As far as I understand, the first part of the process must be done like this: find local maxima and minima....
Duck's user avatar
  • 218
0 votes
1 answer
63 views

Why is the subspace of uniformly rho continuous functions separable?

I am reading through the book of Kosorok on Empirical Processes and I got stuck on a statement that seems to be clear to the author. To me, it is not clear at all. In chapter 6.1 page 87 he states ...
Florian Brück's user avatar
0 votes
0 answers
88 views

Understanding a step in a proof involving an empirical process (machine learning)

I am unable to understand the apparently simple step that yield the display appearing before Lemma B.1. in page 12 of this paper by Chernozhukov et al. (2016). In particular I fail to see how (2.1) ...
rsm's user avatar
  • 190
2 votes
2 answers
352 views

Why are independence and mean-zero necessary for the symmetrization lemma to hold?

I'm going through the proof of the symmetrization lemma (Vershynin), which says $$ \frac{1}{2} E \left\| \sum_i \epsilon_i X_i \right\| \leq E \left\| \sum_i X_i \right\| \leq 2 E \left\| \sum_i \...
Kashif's user avatar
  • 1,497