Application on Lindeberg's condition

Question

Let $_1,_2, … , _$ be a sequence of independent random variables with $(_ = 4^) = (_ = −4^) = \frac12$. Let $_ = _1 + _2 + ⋯ + _$. If $A_n=\sup\, \{ ∈ \Bbb R: (|_| ≥ ) = 1 \}$ for $ ∈ \Bbb N$, show that $A_ = \dfrac23(4^ + 2)$?

I found $E(_)=0$, $\operatorname{Var}(X_n)=16^n$,

for both extreme cases,

$S_=(4/3)(4^-1)$ and $S_=(-4/3)(4^-1)$

I tried to apply Lindeberg's condition,

$\lim_{ \to \infty} (1/\operatorname{Var}(X_))E\left[X_i^2I_{|X_i|≥ ε 4^n\sqrt{n}}\right]$

but I'm stucked on finding the domain to integrate for the integration part and have no idea to proceed...

Answer 1

The minimal value of $\lvert S_n\rvert$ is reached when $X_n=4^n$ and $X_i=-4^i$ for $1\leqslant i\leqslant n-1$, or when $X_n=-4^n$ and $X_i=4^i$ for $1\leqslant i\leqslant n-1$. Indeed, if $X_n=4^n$, we know that $S_n$ is non-negative. To make it as small as possible, the contribution of all the terms in $S_{n-1}$ has to be with a minus sign.

It thus follows that $A_n=4^n-\sum_{i=1}^{n-1}4^i$ and a simple computation gives the announced expression.

Answer 2

$\{r \in \mathbb{R}: \mathbb{P}(|S_n| \geq r) = 1\}$ is a set of lower bounds on $|S_n|$. We can see this because the probability of $|S_n| \geq r$ is $1$, meaning $|S_n|$ is always at or above $r$, and hence $r$ is a lower bound. The supremum of this set is the highest lower bound, i.e. the minimal value of $|S_n|$. Hence, $A_n$ is the minimal value of $|S_n|$. Linedebergs condition tells us when we may approximate a sum of independent variables with finite variance with a normal distribution, it doesn't help us here. Instead, we want to manually calculate the minimal value of $|S_n|$ and prove that it is equivalent to $A_n$ given.

Now that you know this, please pause and attempt to solve it on your own, since there is no actual probability calculation in this problem.

Now that you have (hopefully) attempted to solve this, I will show my proof.

Claim: $A_n = \frac{2}{3} (4^n + 2)$.

Proof: Let $X_i$ and $A_n$ be the values as described in the problem. This value of $A_n$ is achievable if either $X_n = 4^n$ and all $X_i = -(4^i)$, or $X_n = -(4^n)$ and $X_i = 4^i$. WLOG, let $X_n = 4^n$ and $X_i = -(4^i), \forall i < n$. Then, it is clear to see that this is a minimal value, since, changing any value would increase the value of $S_n$, and hence $|S_n|$. The same argument can be made but in the opposite direction for the other possible values. We now seek to prove equality for $-4 - 16 - \ldots + 4^n = \frac{2}{3}(4^n + 2)$. Assume they are uneqal then;

$$\begin{align}-4 -16 - \ldots + 4^n &\not = \frac{2}{3}(4^n + 2) \\-3(4) - 3(4^2) - \ldots + 3(4^n) &\not = 2(4^n) + 4 \\ 4^n &\not= 4(4) + 3(4^2) + \ldots \\& \not= 4^2 + 3(4^2) + 3(4^3) + \ldots \\ &\not= 4(4^2) + 3(4^3) + \ldots \\ &\not =4^3 + 3(4^3) + \ldots\\4^n& \not= 4^n\end{align}$$ Which is a contradiction. Hence, our terms are equal.