0
$\begingroup$

I have been stuck working through the following derivation for a while now (for context the problem is a Central Limit Theorem proof in Stochastic Processes: Theory For Applications, specifically the proof of Theorem 1.7.3).

Problem

The specific issue I am having is in going from (1.87) to (1.88) in the following (quoting directly from the text):

Let $\epsilon = \hat{p} - p$ and $q = 1 - p$. Then: $$ S = (p + \epsilon)ln(1 + \frac{\epsilon}{p}) + (q - \epsilon)ln(1 - \frac{\epsilon}{q}) $$ $$ S = \frac{\epsilon^2}{2p} - \frac{\epsilon^3}{6p^2} + \dots + \frac{\epsilon^2}{2q} + \frac{\epsilon^3}{6q^2} + \dots \tag{1.85}\label{1.85} $$ $$ S = \frac{\epsilon^2}{2pq} - \frac{\epsilon^3}{6p^2} + \dots + \frac{\epsilon^3}{6q^2} + \dots \tag{1.86}\label{1.86} $$ In (1.86) we used the fact that $\frac{1}{p}+\frac{1}{q} = \frac{1}{pq}$. Substituting this into an exponential term: $$exp(-nS) = exp\big(-\frac{n\epsilon^2}{2pq} \big) exp\big( \frac{\epsilon^3}{6p^2} + \dots - \frac{\epsilon^3}{6q^2} + \dots\big)\tag{1.87}\label{1.87}$$ $$exp(-nS) = exp\big(-\frac{n\epsilon^2}{2pq} \big) (1 \pm C_2 n^{-3\alpha + 2}) \tag{1.88}\label{1.88}$$ Where in (1.88) we used, first, the fact that the neglected terms in (1.87) are decreasing at least geometrically with $\epsilon$, second, the condition in the theorem that $|\epsilon| \leq n^{\alpha -1}$, and third, the expansion $e^x = 1 + x + \frac{x^2}{2}+\dots$

Again, my specific issue is in making the jump from (1.87) to (1.88).

My Attempt

I have tried many routes, the most promising of which utilized the property of a geometric series: $$a + ar + ar^2 + \dots = \frac{a}{1 - r}$$

Which, applied to (1.87), seems to show that it is decreasing geometrically at least with $\epsilon$, and has an initial term of $\epsilon^3(\frac{1}{6p^2} - \frac{1}{6q^2})$:

$$r = \epsilon$$ $$a = \epsilon^3(\frac{1}{6p^2} - \frac{1}{6q^2})$$

And hence:

$$\frac{a}{1 - r} = \frac{\epsilon^3(\frac{1}{6p^2} - \frac{1}{6q^2})}{1 - \epsilon}$$

Plugging in $n^{\alpha -1}$ for $\epsilon$ I get:

$$ \frac{(n^{\alpha -1})^3(\frac{1}{6p^2} - \frac{1}{6q^2})}{1 - n^{\alpha -1}}$$

And then letting $C_2 = \frac{1}{6p^2} - \frac{1}{6q^2}$, I arrive at:

$$ \frac{(n^{\alpha -1})^3 C_2}{1 - n^{\alpha -1}}$$

But I am not able to make the final jump to (1.88), which leads me to believe I have made a mistake somewhere in this reasoning.

Any insight into how to go from (1.87) to (1.88) is much appreciated!

$\endgroup$

2 Answers 2

1
$\begingroup$

Your solution is correct. A premise of the theorem is that $\alpha$ is a fixed constant such that $1/2 < \alpha < 2/3$. For such $\alpha$ and large $n$ (as required by the theorem), the expression

$$ \frac{c\cdot n^{3\alpha - 2}}{1 - n^{\alpha - 1}} $$

is a very small number, because both terms $n^{3\alpha-2}$ and $n^{\alpha-1}$ go to zero for large $n$.

Then, as suggested by Gallager, we can use the expansion for $e^x$ for small x.

$$ \exp\left(-\frac{c\cdot n^{3\alpha - 2}}{1 - n^{\alpha - 1}}\right) \approx 1 - \frac{c\cdot n^{3\alpha - 2}}{1 - n^{\alpha - 1}} \approx 1-c\cdot n^{3\alpha-2} $$

At this point, I believe there are typos in the proof because if $\alpha < 2/3$, terms such as $n^{-3\alpha + 2}$ will blow up for large $n$. Also, the original statement of the theorem uses $n^{3\alpha - 2}$.

$\endgroup$
3
  • $\begingroup$ Thank you this is very helpful! I do have two follow up questions now. 1) Gallager drops the term $1 - n^{\alpha -1}$ from the denominator in order to get (1.88). Is this because it approaches 1 more quickly than the numerator approaches 0? 2) Gallager then goes on to state that $\tilde{p}\tilde{q}$ can be represented as $pq(1 \pm n^{-1 + \alpha})$. Can you explain how he arrived at that equivalence? I have been trying but am not able to. $\endgroup$
    – ndake11
    Commented May 21, 2020 at 15:21
  • 1
    $\begingroup$ For (1), it is a simple of limit of quotients. The limit of the numerator is 0, and the limit of the denominator is 1. Regardless of the rates at which the limiting values are approached, for $\epsilon>0$, there exists $n_0$ such that for all $n>n_0$, the numerator and denominator are within $\pm\epsilon$ from 0 and 1, respectively. For (2), you can start with $|k-np| \le n^\alpha$, which is also in the statement of the theorem. $\endgroup$
    – owovrokfop
    Commented May 21, 2020 at 15:32
  • $\begingroup$ I see what you are saying in regards to (1). I am still a bit confused on (2) though. I realize that based on the statement of the theorem we can see that $\epsilon \leq n^{\alpha-1}$. However, when I then try to break $\tilde{p}\tilde{q}$ apart as $(p + \epsilon)(q - \epsilon)$, I get stuck. If I distribute the previous term I arrive at $pq + q\epsilon - p\epsilon - \epsilon^2$, which I am then comparing to $pq(1 \pm n^{\alpha -1})$. I am not able to prove this bound. Am I on the right track or have I made an error in reasoning? $\endgroup$
    – ndake11
    Commented May 21, 2020 at 23:51
1
$\begingroup$

This is not an answer but rather a long comment.

For this kind of problems which require composition of series, I think that it easier to start from where we want to end (!!). For your case $$A=e^{-n S} \implies \log(A)=-n S \tag 1$$ $$S=(p+\epsilon ) \log \left(1+\frac{\epsilon }{p}\right)+(q-\epsilon ) \log \left(1-\frac{\epsilon }{q}\right)$$ $$S=\frac{ (p+q)}{2 p q}\epsilon ^2+\frac{1}{6} \left(\frac{1}{q^2}-\frac{1}{p^2}\right)\epsilon ^3+O\left(\epsilon ^4\right)$$ Now, continuing with Taylor series using $A=e^{\log(A)}$ you will end with $$A=1-\frac{ n (p+q)}{2 p q}\epsilon ^2+\frac{1}{6} n \left(\frac{1}{p^2}-\frac{1}{q^2}\right)\epsilon ^3+O\left(\epsilon ^4\right)$$ which simplify if $p+q=1$ and then write

$$A=1-\frac{ n }{2 p q}\epsilon ^2+\frac{ n(q-p)}{6p^2q^2}\epsilon ^3+O\left(\epsilon ^4\right)$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .