Questions tagged [hoeffdings-inequality]
The hoeffdings-inequality tag has no usage guidance.
26 questions
0
votes
0
answers
32
views
Hoeffding inequality for a product of two random variables
Let $X_1,X_2, \dots, X_{m_1}$, $Y_1,Y_2, \dots, Y_{m_2}$ be $m_1 + m_2$ independent random variables from a probabilistic space $\mathcal{X}$, let $h: \mathcal{X} \to \{-1,1\}$
I'm interested in point ...
- 101
0
votes
0
answers
48
views
Concentration bound for weighted sum of Bernoullis
$\{X_i\}_{i=1,\ldots,n}$ are i.i.d. Bernoulli random variables with parameter $p$. Define
$$Y = \sum_{i=1}^n a_iX_i$$
where $a_i>0$ are known(non-random) constants. I want an upper bound on the ...
- 11
0
votes
0
answers
49
views
Proof of Azuma-Hoeffding inequality for Martingales in MAB
Suppose in an MAB problem, $X_t=\mu+\epsilon_t$ represents the reward values at each period (for a given arm). If $\mathcal{M}(t)$ shows the set of periods until $t$ where a specific arm has been ...
- 693
1
vote
1
answer
58
views
Estimating the sample size for a Binomial proportion to be within an interval with some confidence
I'm studying a Bernoulli random variable $X$ with success probability $p$ which is unknown but satisfies $|p - a| < \epsilon$ for some constants $a$ and $\epsilon$. Given some confidence level $C$, ...
- 227
3
votes
2
answers
155
views
Upper bounds on $\mathbb{P}[X \leq k]$ when $k > \mathbb{E}[X]$, for binomial rand. variable $X$
Let $X$ be a binomial random variable, $X \sim \mathcal{B}(n,p)$.
When $k > \mathbb{E}[X] = np$, are there no Hoeffding-like bounds on the probability $\mathbb{P}[X \leq k]$?
When $k \leq \mathbb{E}...
- 51
3
votes
1
answer
495
views
How to prove error of ensemble model by using the Hoeffding's inequality?
Under Binary classification situation,
error between function $f$ and basic learner(classifier) $h_i(x)$ is
$$P(h_i(x)≠f(x))=\mathcal{E}.$$
It is assumed that $T$ basic classifiers are combined by a ...
- 31
4
votes
1
answer
365
views
Proof of corollary of Hoeffding's inequality
I need to proof a corollary of Hoeffding's inequality, and since I'm not used to doing proofs I really don't know where to begin.
Hoeffding's inequality:
Let $X_1,...,X_n$ be independent real-valued ...
- 43
1
vote
1
answer
103
views
Dose McDiarmid's inequality holds in hilbert space,specially or in $L^2$ space?
Consider McDiarmid's inequality in Hilbert space, or can we extend McDiarmid's inequality to functional data analysis with the complete observed data?
- 11
5
votes
1
answer
568
views
Taylor expansion in Hoeffding's Lemma proof
Hoeffding's Lemma proof uses Taylor expansion with this statement:
From Taylor's theorem, for some $ 0\leq \theta \leq 1$
$ L(h) = L(0) + h L'(0) + \frac{1}{2} h^2 L''(h\theta) \leq \frac{1}{8}h^2 $
...
- 151
3
votes
1
answer
708
views
Why does "Hoeffding's bound greatly overestimates the probability of large deviations for distributions of small variance"?
I've read in a paper using Hoeffding's inequality to derive a bound on the probability of the difference of means of two samples being larger than a threshold that "Hoeffding's bound greatly ...
- 155
2
votes
1
answer
427
views
Is my way of deriving a statistical test from Hoeffding's inequality correct?
I'm trying to deduce from samples of observations from two finite sets of random variables $X_{1}, ..., X_{n}$ and $Y_{1}, ..., Y_{m}$ that the expected values of the average of those random variables ...
- 155
1
vote
0
answers
42
views
$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}...
- 141
3
votes
1
answer
78
views
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 ...
- 187
5
votes
1
answer
527
views
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} = \...
- 185
1
vote
1
answer
114
views
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 ...
- 703
2
votes
0
answers
186
views
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. then
\begin{align*}
P\left(|\bar{X}-E\left[\bar{X}\right]|\geq{}t\right)\leq{}2\exp\left(-\frac{2n^2t^2}...
2
votes
1
answer
446
views
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{\...
- 90
0
votes
0
answers
59
views
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 ...
- 148
1
vote
1
answer
156
views
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 ...
- 90
0
votes
0
answers
67
views
Hoeffding inequality
I came across these questions online :
As known, Learning relies that the Hoeffding inequality holds. In what way?
Can you give an example where it doesn’t hold?
I know what is the meaning of ...
- 27
3
votes
0
answers
79
views
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 ...
- 203
0
votes
0
answers
598
views
Symmetrization in Proof of Hoeffding's Lemma
This alternative proof of a slightly weaker version of Hoeffding's Lemma features in Stanford's CS229 course notes. What's notable about this proof is its use of symmetrization. However, I find this ...
- 161
2
votes
1
answer
774
views
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, ...
user42004
2
votes
1
answer
122
views
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)...
- 3,670
0
votes
0
answers
241
views
Using Hoeffding's inequality on sum of uniform variables
I have the following problem:
$X_1,...,X_n$ are i.i.d. $\sim U(-3,5)$ continuous uniform variables in the support between -3 and 5. $S := X_1 + ... + X_n$.
I need to use Hoeffding's inequality to ...
- 3,670
2
votes
1
answer
795
views
Sample size for estimating success probability of a Bernoulli process
Suppose an AI player in a game can either win or lose. I wish to estimate the win ratio of this player. My question is, how many samples (games) needed in order to get an error smaller than 1%?
A ...
- 473