# Tag Info

28

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 ...

16

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 "... 12 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\... 11 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. 10 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'... 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 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(\... 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$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 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$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 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 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 eventA \cap B = \left\{-c_1 &...

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|$$... 5 For the first part, take x,a,\epsilon>0, and note that$$ \begin{align} |\sqrt{x}-\sqrt{a}|\geq\epsilon &\Rightarrow |\sqrt{x}-\sqrt{a}|\geq\epsilon \frac{\sqrt{a}}{\sqrt{a}} \Rightarrow |\sqrt{x}-\sqrt{a}|\geq\frac{\epsilon\sqrt{a}}{\sqrt{x}+\sqrt{a}} \\ &\Rightarrow |(\sqrt{x}-\sqrt{a})(\sqrt{x}+\sqrt{a})|\geq\epsilon\sqrt{a}\Rightarrow |x-a|\...

5

The class of distributions for which the limiting case of the Chebyshev bound holds is well known (and not that hard to simply guess). Normalized for location and scale it is Z=\begin{cases}-k,&{\text{with probability }}{\:\frac {1}{2k^2}}\\\:0,&{\text{with probability }}1-\frac {1}{k^2}\\\:k,&{\text{with probability }}{\:\frac {1}{2k^2}}\end{...

5

There is no relation between the two quantities $f(\text{Var}[X])$ and $\text{Var}[f(X)]$ for concave $f$. Here are the examples to demonstrate this: Ex 1: Suppose random variable $X$ has the pmf: $p_X(0) = \frac{1}{2}$ and $p_X(4) = \frac{1}{2}$, and $f(x) = \sqrt{x}$. We get $\text{Var}[f(X)] = 1$ and $f(\text{Var}[X]) = f(4) = 2$. So, \$\text{Var}[f(X)] &...

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