Let's consider a random walk with translation $$F(N)=\sum_{n=1}^{N}X(n)$$ Where $X(n)$ is a random variable distribiuted independently and equal to $0$ or $1$.
What is asymptotic growth of $F(N)$?
i.e.
I am looking for function $f$ which satisfy:$$F(N)=O(f(N))$$ Is this true that $f(N)=N^{0.5}$
I hope that someone will help me.
First, notice that $\mu_X=\frac 1 2$ and $\sigma_X=\frac 1 2(0-\frac 1 2)^2+\frac 1 2(1-\frac 1 2)^2=\frac 1 4$.
Let's consider:
$$G(N)=\frac{F(N)}{N}=\frac 1 N \sum_{n=1}^N X(n)$$
By the Central Limit Theorem, as $N\rightarrow \infty $, $G$ becomes normally distributed with $\mu_G=\mu_X=\frac 1 2$ and $\sigma_G=\frac{\sigma_X}{\sqrt N}=\frac{1}{4\sqrt N}$
Now, $F=NG$. Therefore, as $N\rightarrow \infty$, $F$ becomes normally distributed with $\mu_F=N\mu_G=\frac N 2$ and $\sigma_F=N\sigma_G=\frac{\sqrt N}{4}$. Therefore, the expected value of $F$ is $O(N)$ and the standard deviation of $F$ is $O(\sqrt N)$.
In short, in the average-case scenario, $F$ is $O(N)$. Also, in the worst-case scenario, $F=N$, so $F$ is $O(N)$ in worst-case scenario as well.