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.


1 Answer 1


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


$$ \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)}. $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.