Math Problems Vault

Problem 11.1

Let $X$ have a $\operatorname {Bin}(n, p)$ distribution. Define $q: = 1-p$ . For $0 \leq x \leq n q$ , show that

\begin{align} \mathbb {P}\left(X \geq n p+x\right) & \leq \exp \left(-\frac{x^{2}}{2 n p q}\left(q \psi \left(\frac{x}{n p}\right)+p \psi \left(\frac{-x}{n q}\right)\right)\right) \\ & \leq \exp \left(-\frac{x^{2}}{2 n p q} \psi \left(\frac{x(q-p)}{n p q}\right)\right) \end{align}

?

Problem 11.2

Let $X_{1}, \ldots , X_{n}$ be independent random variables with $\mathbb {E}\left[X_{i}\right]: = p_{i}$ and $0 \leq X_{i} \leq 1$ for each $i$ . Let $p: = \left(p_{1}+\cdots +p_{n}\right) / n = : 1-q$ . Show that

\mathbb {P}\left(\sum _{i \leq n} X_{i} \geq n p+x\right) \leq \exp \left(-\frac{x^{2}}{2 n p q} \psi \left(\frac{x(q-p)}{n p q}\right)\right) \quad \text{ for } 0 \leq x \leq n q

?

Problem 11.3

(i)(ii)

Suppose $X$ has a Poisson ( $\lambda$ ) distribution.

?

(i)

By direct minimization of $\exp (-t(\lambda +x)) \mathbb {E}\left[\exp (t X)\right]$ over $\mathbb {R}^{+}$ , prove that

\mathbb {P}\left(X \geq \lambda +x\right) \leq \exp \left(-\frac{x^{2}}{2 \lambda } \psi \left(\frac{x}{\lambda }\right)\right)

(ii)

Derive the same tail bound by a passage to the limit in the binomial bound from Problem [1].

Problem 11.4

For each random variable $X$ with finite variance, and each constant $M$ , show that $\operatorname {Var}\left[\tau (X, M)\right] \leq \operatorname {Var}\left[X\right]$ , with $\tau$ as defined in $\langle 26 \rangle$ : for a constant $M > 0$ , $\tau (x, M): = -M\left\{ x < -M\right\} +x\left\{ \left|x\right| \leq M\right\} +M\left\{ x > M\right\}$ , the truncation of $x$ to $[-M, M]$ .

?

Problem 11.5

(i)(ii)

Let $\left\{ X_{n}\right\}$ be a sequence of independent, identically distributed two-dimensional random vectors with $\mathbb {E}\left[X_{i}\right] = 0$ and $\operatorname {Var}\left[X_{i}\right] = I_{2}$ . Define $S_{n} = X_{1}+\ldots +X_{n}$ .

?

(i)

Show that $\lim \sup \left|S_{n}\right| / L_{n} \leq 1$ almost surely.

(ii)

Show that, with probability one, the sequence $S_{n} / L_{n}$ visits every open subset of the unit ball $\left\{ \left|x\right| < 1\right\}$ infinitely often. Hint: Project three-dimensional random vectors.