Hello,

Consider the set of binary sequences of length $N$ having $Np$ $1$'s and $N(1-p)$ $0$'s $(0 < p < 1)$. This set is sometimes called a typical set, denoted by $T(P)$, and defined as

$T(P) = (x^N: P_{x^N} = P)$

where $x^N = (x_1,...,x_N)$ is a binary sequences of length $N$, $P = [p 1-p]$, and $P_{x^N}$ is the empircal distribution defined as (for the binary case)

$P_{x^N}(1) = \frac{\sum_{i=1}^N x_i}{N}$,

and

$P_{x^N}(0) = 1-\frac{\sum_{i=1}^N x_i}{N}$.

Suppose we are selecting, uniformly at random, one sequence from this set.

I want to show that with probability tending to $1$ as $N\to\infty$, both the first half and the second half of this sequence (both of length $N/2$) are approximately has a fraction of $1$'s between $p(1-\epsilon)$ and $p(1 + \epsilon)$ for some arbitrarily small $\epsilon>0$.

Thank you!

Hello,

Consider the set of sequences of zeroes and ones of length $N$ with $k$ ones (or, Np ones where $p=k/N$). We draw randomly and uniformly a sequence from this set.

I want to show that with probability tending to $1$ as $N→∞$, there are approximately $kN/2$ (or $Np/2$) ones in the first half of this sequence.

Thank you!

SOLVED