Questions tagged [hoeffdings-inequality]

The tag has no usage guidance.

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

Tight error bound for Possion sampling to estimate a real-valued mean without knowledge of variance

I am trying to develop a tight bound on the sampling error of a Poisson sampling (sampling with non-uniform probabilities). I have a set of real-valued data $X$ with finite size $N$ and I want to ...
2
votes
1answer
50 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{\...
0
votes
0answers
38 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 ...
0
votes
1answer
38 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 ...
0
votes
0answers
33 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 ...
4
votes
0answers
27 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 ...
0
votes
0answers
22 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 ...
1
vote
1answer
28 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, ...
0
votes
0answers
7 views

Analysis of large deviations of the empirical survival function

I have been doing some self studying in survival analysis, but I seem to be stuck on this book problem. It's asking us to use the Hoeffding's Inequality for the analysis of large deviations of the ...
2
votes
1answer
49 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)...
0
votes
0answers
17 views

Why can information gain be used in Hoeffding Inequality as mean?

The Hoeffding inequality $$P(|\mu-\bar{X}|>\epsilon) \leq 2exp(-2n\epsilon^{2}/(b-a)^2)$$ with real mean $\bar{X}$ and sample mean $\mu$ is used in Hoeffding trees to determine the best feature to ...
0
votes
0answers
24 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 ...