# Tag Info

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}... 16 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 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'... 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 ... 9 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(\... 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$bare 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 > ... 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 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 ... 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 If we letX_1, \ldots, X_n \stackrel{\text{i.i.d.}}{\sim}$Bernoulli$(p)$, then since$X_i \in [0, 1]$for each$i$Hoeffding's inequality says that $$P(|\bar{X} - p| \geq t) \leq 2 e^{- 2n t^2}$$ or $$P(|\bar{X} - p| < t) \geq 1 - 2 e^{- 2n t^2} .$$ If we want a$95\%$confidence interval say, we can equate the right hand side to$0.95$and solve ... 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$Bpositive 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 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 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 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 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 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 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 ... 5 I know it's stated in the problem, but I figured I'd put it in the answer bank: For some line$cx+d$that cuts through$\frac{1}{X}$at the points x=a and x = b, it's easy to show that$ c = - \frac{1}{ab} $and$d = \frac{a+b}{ab} $, So,$ \frac{1}{X} \le - \frac{1}{ab} X + \frac{a+b}{ab} $, and therefore: $$E(\frac{1}{X}) \le - \frac{1}{ab} E(X) + \... 5 Once we observe that both sides of the inequality are scale invariant, it follows immediately by combining two simple, well-known inequalities, of which the most notable is that correlation coefficients cannot be less than \newcommand{\e}{\mathbb{E}}-1. The Cauchy-Schwarz Inequality guarantees that the correlation coefficient \rho(X,Y) of any two random ... 5 We are given that$$\lim_{n \rightarrow \infty}P(|X_n-\alpha| > \epsilon) = 0$$and we want to show that$$\lim_{n \rightarrow \infty}P\left(\left|\frac {\alpha}{X_n}-1\right| > \epsilon\right) = 0$$We have that$$\left|\frac {\alpha}{X_n}-1\right| = \left|\frac {1}{X_n}(\alpha-X_n)\right| = \left|\frac {1}{X_n}\right|\left|X_n-\alpha\right|$\$ ...