In the book Probability by Leo Breiman, the author states the following.
From stirling's approximation, we have ${2n\choose n} = 2^{2n}.\frac{1}{\sqrt{n\pi}}(1+\delta_n)$. In conclusion, As $n$ becomes large, the proportion of the sequences such that heads come up exactly n/2 times goes to zero.
Whatever the "law of averages" may say, it is certainly not reasonable in a thousand tosses of a fair coin to expect exactly 500 heads. It is not possible to fix a number $M$ such that for $n$ large most of the sequences have the property that the number of heads in the sequence is within $M$ of $\frac{n}{2}$. For $2n$ tosses this fraction of the sequences is easily seen to be less than $\frac{2M}{\sqrt{n\pi}}$(forgetting $\delta_n$) and so becomes smaller and smaller.
The best we can get is that usually the proportion of heads in $n$ tosses is close to $\frac{1}{2}$.
My question is how is most sequences having the property that number of heads lying in between $\frac{n}{2}+M$ and $\frac{n}{2}-M$ different from the proportion of heads being close to half. How is the probability changing from nearly 0 (i am assuming $\frac{2M}{\sqrt{n\pi}}$ comes from union bound) to 1. Please help me understand this. Thank you.
As correctly noted in the OP, if we neglect the error term of Stirling approximation, as $n$ increases the probability to get $h=n$ heads in $2n$ tosses is
$$P[h=n]\\=\binom{2n}{n}2^{-2n}\approx \frac{\sqrt{4\pi n}\,(2n/e)^{2n}}{ {2\pi n}\, (n/e)^{2n} \,\,2^{2n} }=\frac{1}{\sqrt{\pi n}}$$
On the other hand, the probability that the number of heads falls within the interval $n\pm M$ is
$$P[n-M\leq h\leq n+M]\\=\binom{2n}{n}2^{-2n}+2 \sum_{k=1}^M \binom{2n}{n+k}2^{-2n} $$
Each term of the summation can be approximated as
$$ \binom{2n}{n+k}2^{-2n} \approx \frac{\sqrt{4\pi n}\,(2n/e)^{2n}}{ {2\pi \sqrt{n^2-k^2}}\, (n^2-k^2)^n/e^{2n} \,\,2^{2n} }=\frac{n^{2n+1/2}}{ \sqrt{\pi}\, (n^2-k^2)^{n+1/2} } $$
For $M$ constant, as $n\rightarrow \infty$ each term is $O(n^{-1/2})$. So the probability that the number of heads is within the interval $n\pm M$ is $O(n^{-1/2})$ as well, and then tends to zero. In other words, as $n$ increases, $M$ becomes neglectable, so the whole expression asymptotically tends to $\displaystyle \frac{1}{\sqrt{\pi n}}$.
To obtain a range whose probability no longer tends to zero, $M$ has to grow with $n$. In particular, since the summation includes $2M+1$ terms of magnitude $O(n^{-1/2})$, the growth rate of $M$ has to be at least equal to $O(n^{1/2})$.