We’re rewarding the question askers & reputations are being recalculated! Read more.
26

Yes, we can get an analogous result using the sample mean and variance, with perhaps, a couple slight surprises emerging in the process. First, we need to refine the question statement just a little bit and set out a few assumptions. Importantly, it should be clear that we cannot hope to replace the population variance with the sample variance on the right ...


20

For convenience, let $X$ denote a continuous zero-mean random variable with density function $f(x)$, and consider $P\{X \geq a\}$ where $a > 0$. We have $$P\{X \geq a\} = \int_a^{\infty}f(x)\,\mathrm dx = \int_{-\infty}^{\infty}g(x)f(x)\,\mathrm dx = E[g(X)]$$ where $g(x) = \mathbf 1_{[a,\infty)}$. If $n$ is an even integer and $b$ any positive real ...


16

I’m not sure I understood your question correctly. I’ll try to answer: try to write $$-\frac{a}{b-a} e^{tb} + \frac{b}{b-a} e^{ta}$$ as a function of $u = t(b-a)$ : this is natural as you want a bound in $e^{u^2 \over 8}$. Helped by the experience, you will know that it is better to chose to write it in the form $e^{g(u)}$. Then $$e^{g(u)} = -\frac{a}{b-a} ...


15

This is just a complement to @cardinal 's ingenious answer. Samuelson Inequality, states that, for a sample of size $n$, when we have at least three distinct values of the realized $x_i$'s, it holds that $$x_i-\bar x < s\sqrt{n-1},\;\; i=1,...n$$ where $s$ is calculated without the bias correction, $s= \left (\frac 1n\sum_{i=1}^n(x_i-\bar x)^2\right)^{1/2}...


15

We can draw a connection to Hoeffding's inequality in a fairly direct way. Note that we have $$ \{ Z > \theta + \epsilon\} = \big\{\sum_i X_i Y_i > (\theta + \epsilon)\sum_i Y_i \big\} = \big\{ \sum_i (X_i - \theta - \epsilon) Y_i > 0 \} \>. $$ Set $Z_i = (X_i - \theta - \epsilon)Y_i + \epsilon/2$ so that the $Z_i$ are iid, $\mathbb E Z_i = 0$ ...


15

This indeed can be proven by Jensen inequality. Hint: Note that for $\alpha > 1$ the function $x^{\alpha}$ is convex in $\left[0, -\infty\right)$ (That's where you use the assumption $X \ge 0$). Then Jensen inequality gives $$ \mathbb{E}\left[Y\right]^{\alpha} \le \mathbb{E}\left[Y^{\alpha}\right] $$ and for $\alpha < 1$, it is the other way arround. ...


13

The details of the proofs matter less than developing appropriate intuition and techniques. This answer focuses on an approach designed to help do that. It consists of three steps: a "setup" in which the assumption and definitions are introduced; the "body" (or a "crucial step") in which the assumptions are somehow related to what is to be proven, and the "...


11

You need to reformulate this in terms of random variables $X$ and $Y$. The reasoning is that if $X+Y\geq 0$, then either $X\geq 0$ or $Y\geq 0$; it can't be that both $X$ and $Y$ are negative. Hence, the event $$ \{X+Y\geq 0\} $$ is a subset of $$ \{X\geq 0\}\cup\{Y\geq 0\}. $$ Since $\Pr(\;\cdot\;)$ is a monotonic set function, we have $$ \Pr\{X+Y\...


10

Your class is using needlessly complicated expressions for the Chernoff bound and apparently giving them to you as magical formulas to be applied without any understanding of how they came about. Suppose that $X$ is a random variable for which we wish to compute $P\{X \geq t\}$. One way of doing this is to define a real-valued function $g(x)$ as follows: $...


10

Look at the sequence of random variables $\{Y_n\}$ defined by retaining only large values of $|X|$: $$Y_n:=|X|I(|X|>n).$$ It's clear that $Y_n\ge nI(|X|>n)$, so $$E(Y_n)\ge nP(|X|>n).\tag1$$ Note that $Y_n\to0$ and $|Y_n|\le |X|$ for each $n$. So the LHS of (1) tends to zero by dominated convergence.


9

Yes, see Theorem 6.21 of [LT13], Michel Ledoux and Michel Talagrand. Probability in Banach Spaces: isoperimetry and processes, volume 23. Springer Science & Business Media, 2013. For simplicity you may also look at section 8 of my paper. http://arxiv.org/pdf/1507.06370v2.pdf (I just summarized those theorems -- the purpose of the paper is completely ...


8

If $X$ and $Y$ are independent random variables such that we have $P\{X > x\} = a$ and $P\{Y > y\} = b$ where $x$, $y$, $a$, and $b$ are numbers known to us, then $$\begin{align*} P\left(\{X > x\} \cup \{Y > y\}\right) &= P\{X > x\} + P\{Y > y\} - P\{X > x, Y > y\}\\ &= P\{X > x\} + P\{Y > y\} - P\{X > x\}P\{Y > ...


8

Defining $Y=X-\mathbb{E}[X]$, it follows that $\mathbb{E}[Y]=0$ and $\mathbb{Var}[Y]=\mathbb{Var}[X]=:\sigma^2=\mathbb{E}[Y^2]$. For $t,u>0$, using Markov's inequality, we have $$ \Pr(Y\geq t) = \Pr(Y+u\geq t+u) \leq \Pr((Y+u)^2\geq (t+u)^2) $$ $$\leq \frac{\mathbb{E}[(Y+u)^2]}{(t+u)^2} = \frac{\sigma^2+u^2}{(t+u)^2}=:\varphi(u). $$ Minimize: $\varphi'...


8

I'll try to explain it in linear case. Consider the linear model $$Y_i=\sum_{j=1}^{p} \beta_jX_{i}^{(j)}+\epsilon_i, i=1,...,n. $$ When $p \leq n$ (number of independent variables less or equal then number of observation) and design matrix has full rank, the least squared estimator of $b$ is $$\hat{b}=(X^TX)^{-1}X^TY$$ and prediction error is $$ \dfrac{\| X(\...


7

Answer by Dilip Sarwate and cardinal: $F^{*2}(x)=P(X+Y \leq x) \leq P(X \leq x, Y \leq x)=F^{2}(x).$ Thank you very much!


7

Note the limits. Since we're integrating from a lower limit of $\theta E(X)$, it must be that $x\geq \theta\, E(X),\: $ for $\:\theta\, E(X) \leq x<\infty$. From that it should be clear.


6

Adjusting the notation of Wasserman's notes a little bit, I presume that the problem may be restated like this. You have $Y^{(i)}_1,\dots,Y^{(i)}_n$ independent and identically distributed $Ber(p^{(i)})$, for $i=1,\dots,m$. Define the estimates $\hat{p}^{(i)}_n=(1/n)\sum_{j=1}^n Y^{(i)}_j$, for $i=1,\dots,m$. Then, using subadditivity and Hoeffding's ...


6

$\mathbb{E}(V_{i} | X_{1}, \ldots, X_{i-1}) = 0$ Let us introduce some notation, $X_{1:i} = X_{1}, \ldots, X_{i}$. \begin{align*} \mathbb{E}(V_{i} | X_{1:i-1}) &= \mathbb{E}\left( \[\mathbb{E}(g | X_{1:i}) - \mathbb{E}(g | X_{1:i-1})\] | X_{1:i-1}\right) \\\\ &=\mathbb{E}\left( \mathbb{E}(g | X_{1:i}) | X_{1:i-1}\right)- \mathbb{E}\left( \mathbb{...


6

It doesn't. Let $X$ be the outcome of a die roll. $P(X=2|X \text{ is even})=\frac{1}{3}$ $P(X=2|X \text{ is even or odd})=\frac{1}{6}$ However, this isn't a case of gaining more information. I'm fairly certain $H(X|B)\leq H(X|B \cup C)$ where $H$ denotes Shannon information (a measure of information/uncertainty).


6

Details to take care of the $N=0$ case. $$ \begin{align} \{Z\geq\theta+\epsilon\} &= \left(\{Z\geq\theta+\epsilon\} \cap \{N=0\}\right) \cup \left(\{Z\geq\theta+\epsilon\} \cap \{N>0\}\right) \\ &= \left(\{0\geq\theta+\epsilon\} \cap \{N=0\}\right) \cup \left(\{Z\geq\theta+\epsilon\} \cap \{N>0\}\right) \\ &= \left(\emptyset \cap \{N=0\}...


6

You've got a random variable $\bar X_n \sim \mathcal N(\mu, \sigma^2/n)$ and you're looking to quantify the probability that $\bar X_n$ is a certain distance from its mean. This means you'll want to make use of a concentration inequality. I'm going to prove a result that is very similar to your question but with some modifications so that it is actually ...


6

I am able to use Cauchy-Schwartz inequality, but I not quite getting the same result. I may have made a mistake, so here are all the steps. Note that for positive semi-definite matrices, trace defines an inner product. That is $tr(AB) = \langle B^T, A \rangle$. Then by Cauchy-Schwarz for $A$ and $B$ positive semi-definite symmetric matrices, $$tr(AB) = \...


6

as pointed out in the comments by @zhanxiong, the triangle inequality is sufficient here, take: $|X_1 -X_2| \leq |X_1| +|X_2|$ and take expectations to get $\mathbb{E}(|X_1 -X_2|) \leq \mathbb{E}(|X_1|) +\mathbb{E}(|X_2|)$. However, you cannot equate the two marginal expectations to be the same value without assuming they have the same marginal ...


5

The expected time until the sequence is terminates is infinite. In fact, not only is the expected value of $\text{min}\{t : Y_t>(p+\delta)t\}$ infinite for any $\delta>0$, but even the expected value of $\text{min}\{t : Y_t > pt + \delta\}$ is infinite. This can be proven using the optional sampling theorem (also known as optional stopping ...


5

You don't have to use the standard normal distribution. The same is true for the Central Limit Theorem. Some people prefer normalizing the sum because they feel that it makes the result simpler to state.


5

For $c_1 < c_2$, the event $\left\{|X|_{(1)} < c_1, |X|_{(2)} < c_2\right\}$ is the union of the two events $$\begin{align} A &= \left\{-c_1 < X_{1} < c_1, -c_2 < X_{2} < c_2\right\}\\ B &= \left\{-c_2 < X_{1} < c_2, -c_1 < X_{2} < c_1\right\} \end{align}$$ whose intersection is the event $A \cap B = \left\{-c_1 &...


5

It appears as the standard method of proof that $(\mathbb{E}X)^2 \leq \mathbb{E}X^2$, so $\mathbb{E}X \leq \sqrt{\mathbb{E}X^2}$. That's how all those square roots get there in the last three lines. C-S is hidden in there, admittedly, and you have to rearrange the $\mathbb{E}\dots \textbf{I}_{stuff}$ into probabilities, but that's the core of it.


5

I can't answer the first part of your question, but as for extending it to random variables with nonzero means... First, note that any r.v. $Z$ with finite range $[a+\mu,b+\mu]$ and (necessarily finite) mean $\mu$ can be transformed into an r.v. $X = Z-\mu$ that is, of course, zero mean with range $[a,b]$ (thus satisfying the conditions in your problem ...


5

Yes Jensen inequality holds for multiple variable. We can find a general formulation in the mesure theoretic article in Wikipedia. "Let (Ω, A, μ) be a measure space, such that μ(Ω) = 1. If g is a real-valued function that is μ-integrable, and if g is a convex function on the real line. $$\varphi\left(\int_\Omega g\, d\mu\right) \le \int_\Omega \varphi \...


5

This answer keeps mutating. The current version does not relate to the discussion I had with @cardinal in the comments (although it was through this discussion that I thankfully realized that the conditioning approach did not appear to lead anywhere). For this attempt, I will use another part of Hoeffding's original 1963 paper, namely section 5 "Sums of ...


Only top voted, non community-wiki answers of a minimum length are eligible