-)We have a mathematically model of a random walk on the integer number line $ {\displaystyle \mathbb {Z} } $ , which starts at $0$ and at each step moves $+1$ or $−1$ with equal probability of 1/2. $\Omega:= \{\pm 1\}^N= \{ \omega=(x_1,..,x_N)|x_j \in \{\pm 1\}\}$ , $X_k(\omega):=x_k$..what we do in the kth step . For $n \le N$: $S_n(\omega):=\sum_{k=1}^n X_k (\omega)$ .. where we are after n steps. All paths have the same probability so it is a laplace modell.
We already show that $ k \rightarrow P(S_n=k)$ have his max in $k=0$ for n even and in $k=+1,-1$ for n odd with $P(S_{2n}=0)=P(S_{2n-1}=\pm1)= \binom{2n}{n} \frac{1}{2^{2n}}$
We define $ \tau_a (\omega):= min \{ n >0| S_n(\omega)=a\}, \tau_a=N+1$ for a empty set and already showed $P(\tau_a \le n)= P(S_n \not\in (-a,a])$ for $a \not=0, n \le N $.
Now we should estimate the expectation value of $\tau_a$ for $a>0$:
$E(\tau_a)= \sum_{n=1}^{N+1} n* P(\tau_a=n)= \sum_{n=0}^N P(\tau_a>n)= \sum_{n=0}^N P(S_n \in (-a,a])\ge \sum_{n=1}^N P(S_n \in \{0,1\})=\sum_{n=1}^N \binom{2n}{n} \frac{1}{2^{2n}}$
Now i use stirling:
$\binom{2n}{n} \frac{1}{2^{2n}}= \frac{(2n)!}{(n!)^2*2^{2n}}= \frac{\sqrt{4 \pi n} (\frac{2n}{e})^{2n} *(O(\frac{1}{2n}) +1)}{(O(1/n)+1)^2* 2\pi n (\frac{n}{e})^{2n}*2^{2n}}$= $\frac{1}{\sqrt{\pi*n} (1+ O(\frac{1}{n}))}$
So i get above $\sum_{n=1}^N \binom{2n}{n} \frac{1}{2^{2n}}= \sum_{n=1}^N \frac{1}{\sqrt{\pi*n} (1+ O(\frac{1}{n}))}=\sum_{n=1}^N \frac{1+ O(\frac{1}{n}))}{\sqrt{\pi*n}} $
Question: How they came in the script to a constant C so that: $ E(\tau_a) \ge \sum_{n=1}^N \frac{C}{\sqrt{\pi n}}$
I think of a calculation like: $\frac{1}{\sqrt{\pi*n} (1+ O(\frac{1}{n}))}=\frac{1}{\sqrt{\pi*n} (1+ O(1))} \le \frac{1}{\sqrt{\pi*n} (1+ C)}=\frac{(1+C)^{-1}}{\sqrt{\pi*n}}$