Statistical Analysis Stack Exchange
Statistical Analysis Stack Exchange

Questions tagged [hoeffdings-inequality]

18 questions
4
votes
1 answer

Hoeffding type concentration result for the inverse of a sum of iid random variables

Consider a collection of $n$ i.i.d. Bernoulli random variables $\{ X_i \}_{i=1}^{n}$ with $\mathbb{E}[X_i] = \mu$. Then, if $\hat{\mu}$ is the mean of the $n$ random variables, i.e. if, $$\hat{\mu} = \frac{1}{n} \sum_{i=1}^{n} X_i,$$ then, by…
ijuneja
  • 145
  • 5
3
votes
0 answers

Prove or disprove a concentration result of the norm of high dimensional random vector

Suppose that $X = (X_1,X_2,\cdots ,X_n)$ is a vector, where $X_i, i=1,2,\cdots ,n$ are independent and sub-gaussian random variables satisfying $\mathbb{E}[X_i^2] = 1$. Prove or disprove the following claim: $\left| \mathbb{E}\|X\|_2-\sqrt{n}…
j200932
  • 163
  • 3
2
votes
1 answer

Probability that a Linear Combination of Dirichlet Random Variables is a Distribution

I've been putting a lot of thought on this problem, but it seems I ran out of ideas. Any help would be appreciated! Suppose we generate two probability vectors $\boldsymbol{\theta}_1, \boldsymbol{\theta}_2 \sim \operatorname{IID…
JFarias
  • 80
  • 6
2
votes
1 answer

Expectation of (sum subtract the expectation of sum)

Let's say we have random variables $\mathbf{X}$, and we have $P(\mathbf{X}\in [a, b])=1$, we have $\mathbf{S}_n = \mathbf{X}_1 + \mathbf{X}_2, +\dots + \mathbf{X}_n$. If $\mathbf{X}_1, \mathbf{X}_2, \dots, \mathbf{X}_n$ are independent, I believe…
user42004
2
votes
1 answer

Bounding the structural-risk-minimization (using Hoeffding's inequality twice)

tl;dr: The main question is if I use an inequality that is true with a certain probability (confidence) twice, do I get the same confidence? Original: I've got the following exercise: Where $e_p(h)$ denotes the true 0-1 loss of the hypothesis $h$…
Maverick Meerkat
  • 2,147
  • 14
  • 27
1
vote
0 answers

$L^2$ convergence of inverse

Let $h$ be some bounded non-negative function. Assume that some random quantity $\mu^N (h)$ be some random quantity with almost sure limit $\mu(h) > 0$. For instance we could have $\mu^N(h) = N^{-1} \sum_{i = 1}^N h(X^i)$ with $X^{1:N}…
yprobnoob
  • 131
  • 3
1
vote
0 answers

Hoeffding's inequality implementation wrong?

I've learned Hoeffding'e inequality from Wikipedia, and to check if I understand correctly the formula, I refer to this lecture for exact example that I can solve. But why do I think I get a different result with this lecture? The example in the…
narip
  • 97
  • 6
1
vote
1 answer

Normal approximation and Hoeffding bound

Hoeffding bound for any $\epsilon>0$ is: $$P_F(|\bar{X}_n-\mu(F)|\geq \epsilon)\leq 2 \exp\{-\frac{n\epsilon^2}{2}\}=h(\sqrt{n}\epsilon)$$ wherever $|X|<1$. Now I want to have a comparison between this normal approximation and Hoeffding bound. I…
statwoman
  • 541
  • 1
  • 9
1
vote
0 answers

Hoeffding's inequality for high dimensional data, particularly when p>>n

In one dimension, if $X_i\in\left[a_i,b_i\right]$, $i\in\left\{1,\ldots{},n\right\}$, are i.i.d.…
Jonathan Mitchell
  • 83
  • 5
0
votes
0 answers

Sample size for using Hoeffding inquality

right now I am stuck on problem. I need to find the sample size for an experiment with Hoeffdings inequality. I want to know how many people I should sample so that the estimate differs from the true porption at most by 0.1 with a probability more…
SuperDieter
  • 1
0
votes
0 answers

Test for mean 0 based on Bennett inequality?

Bennett's inequality provides a bound on the probability for the sum of bounded mean 0 random variables to exceed a specified value. It makes no assumptions about distribution, and is stronger than Hoeffding's inequality since it uses the variance…
Kenneth Harris
  • 101
0
votes
0 answers

How do I reconcile a flipped sign in the Hoeffding's inequality derivation of UCB?

In the language of bandit theory, let's suppose we have some action value $q(a)$ which is the expected value of the reward yielded from choosing action $a$. We also have some estimate of what $q(a)$ should be, called $Q(a)$, which is just an average…
Richard
  • 133
  • 5
0
votes
0 answers

Hoeffding like result for expected number of pulls

Hoeffding's inequality states that if, $X_1, \ldots, X_n$ are independent random variables bounded by the interval $[0, 1]$, i.e. $0 ≤ X_i ≤ 1$. And the empirical mean of these variables is given by, $$\overline X = \frac{1}{n}(X_1 + \cdots +…
ijuneja
  • 145
  • 5
0
votes
0 answers

Proof (requested) of sample sizes in multivariate distribution

My team has been asked to build a predictive model. We have a very limited dataset, but using a number of rationalizations about bounds on the data and the current behavior (54 data points) I have constructed a Gaussian Process of variable X that…
Michael Tamillow
  • 148
  • 5
0
votes
1 answer

Linear combination of Random Variables less than Zero and Hoeffding's inequality

Let $X_1$ and $X_2$ be Uniform Random Variables and set $$X = aX_1 + bX_2, $$ with $a \geq 0$ and $b \leq 0$. I'd like to bound $P(X \leq 0)$ using Hoeffding's inequality. How do I do that? P.S.: I know we can compute $P(X)$ exactly, but I'd like to…
JFarias
  • 80
  • 6
1
2