# Using the martingale central limit theorem

Suppose a box has $2n$ tickets half of which are labelled $+1$ and half $-1$. Labeling the draws without replacement by $X_1, ...$, define $S_m = X_1 + ... + X_m$. For any $t \in (0,1)$

$S_{\frac{[2nt]}{\sqrt n}} \rightarrow^D N(0, v_t^2)$

where $[\;]$ denotes the greatest integer function and some $v_t$ depending on $t$.

I've been told that there is a martingale $Y_k := \frac{S_1}{2n-1} + ... + \frac{S_k}{2n-k}$, but I'm not seeing how to show this.

Let $F_k := \sigma(X_1, ... X_k).$ Then $\Bbb E(Y_k\; |\; F_{k-1}) = \Bbb E(Y_{k-1}\; |\; F_{k-1}) + \Bbb E(\frac{S_k}{2n-k}|\; F_{k-1} ) = Y_{k-1} + \Bbb E(\frac{S_k}{2n-k}\;|\; F_{k-1} )$.

I don't see how the last term vanishes, and even if it did it's not really clear to me how to use central limit theorem. Any hints or starting points would be much appreciated.

Let $$a_{m}=\sum_{i=1}^{m}X_i1\{X_i=1\}$$ and $$b_{m}=-\sum_{i=1}^{m}X_i1\{X_i=-1\}$$. Then $$a_m+b_m=m$$ and $$a_m-b_m=S_m$$. Solving this system, one gets

$$a_m=\frac{m+S_m}{2}\quad\text{and}\quad b_m=\frac{m-S_m}{2}$$

so that the probability of getting $$1$$ in step $$m+1$$ given $$S_m$$ is

$$\mathsf{P}(X_{m+1}=1\mid S_m)=\frac{n-a_m}{2n-m}=\frac{1}{2}-\frac{S_m/2}{2n-m}.$$

Hence,

$$\mathsf{E}[X_{m+1}\mid \mathcal{F}_m]=-\frac{S_m}{2n-m},$$

and $$Y_{n,m}:=\frac{S_m}{2n-m}$$ is a martingale because (for $$m<2n-1$$)

$$\mathsf{E}\left[\frac{S_{m+1}}{2n-(m+1)}\mid \mathcal{F_m}\right]=\frac{1}{2n-(m+1)}\times\frac{2n-(m+1)}{2n-m}S_m=\frac{S_m}{2n-m}.$$

Let $$m_n=[2nt]$$, write

\begin{align} S_{m_n}&=\left(S_{m_n}-\frac{2n-m_n}{2n-m_n+1}S_{m_n-1}\right) \\ &\quad +\left(\frac{2n-m_n}{2n-m_n+1}\right)\left(S_{m_n-1}-\frac{2n-m_n+1}{2n-m_n+2}S_{m_n-2}\right)+\dots, \end{align}

which is the sum of a MDS, and use Theorem 4 from these lecture notes (actually, this question appears in the problem set accompanying these notes). Specifically, using the notation from the link for $$S_{m_n}/\sqrt{n}$$ we get \begin{align} n\times V_{n,m_n}^2&=\left(1-\frac{S_{m_n-1}^2}{(2n-m_n+1)^2}\right)\\ &\quad +\left(\frac{2n-m_n}{2n-m_n+1}\right)^2\left(1-\frac{S_{m_n-2}^2}{(2n-m_n+2)^2}\right)+\dots \end{align}

Then using the expression for $$\mathsf{E}S_m^2=m(2n-m)/(2n-1)$$ we find that $$V_{n,m_n}^2=v_t^2+o_p(1), \quad\text{ where }\quad v_t=\sqrt{2t(1-t)}.$$