# Questions tagged [hoeffdings-inequality]

The tag has no usage guidance.

27 questions
Filter by
Sorted by
Tagged with
28 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
38 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 ...
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 ...
• 683
1 vote
55 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
141 views

• 141
74 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
502 views

• 90
65 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
77 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
564 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
758 views

• 3,560
235 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,560