6. Let $\xi_{1}, \ldots, \xi_{N}$ be independent Bernoulli random variables, $\mathrm{P}\left\{\xi_{i}=1\right\}=p, \mathrm{P}\left\{\xi_{i}=-1\right\}=1-p, S_{i}=\xi_{1}+\ldots+\xi_{i}, 1 \leqslant i \leqslant N$, $S_{0}=0$. Let $\mathscr{R}_{N}$ be the range, i.e., the number of distinct points visited by the random walk $S_{0}, S_{1}, \ldots, S_{N}$.

Find $\mathrm{E} \mathscr{R}_{N}$. Determine for which values of $p$ the law of large numbers in the form

$$
\mathrm{P}\left\{\left|\frac{\mathscr{R}_{N}}{N}-c\right|>\varepsilon\right\} \rightarrow 0, \quad N \rightarrow \infty
$$

holds, where $\varepsilon>0$ and $c$ is some constant.
Solution. Let's represent $\mathscr{R}_{N}$ in the following form:

$$
\begin{aligned}
\mathscr{R}_{N}=1+I\left(S_{1} \neq 0\right)+I\left(S_{2} \neq\right. & \left.0, S_{2} \neq S_{1}\right)+\ldots \\
& \ldots+I\left(S_{N} \neq 0, S_{N} \neq S_{1}, \ldots, S_{N} \neq S_{N-1}\right)
\end{aligned}
$$

Let $V_{n}^{N}=\sum_{k=0}^{n-1} \xi_{N-k}$, then

$\mathscr{R}_{N}=1+I\left(V_{1}^{1} \neq 0\right)+I\left(V_{1}^{2} \neq 0, V_{2}^{2} \neq 0\right)+\ldots+I\left(V_{1}^{N} \neq 0, \ldots, V_{N}^{N} \neq 0\right)$. Since

$$
\mathrm{P}\left\{V_{1}^{i} \neq 0, \ldots, V_{i}^{i} \neq 0\right\}=\mathrm{P}\left\{S_{1} \neq 0, \ldots, S_{i} \neq 0\right\}, \quad i=1, \ldots, N
$$

we obtain that

$$
\mathrm{E} \mathscr{R}_{N}=1+\sum_{k=1}^{N} \mathrm{P}\left\{S_{1} \neq 0, \ldots, S_{k} \neq 0\right\}
$$

Notice that on odd steps $S_{k}$ cannot be zero, so

$$
\mathrm{E} \mathscr{R}_{N}=1+\sum_{k=1}^{[N / 2]} \mathrm{P}\left\{S_{2} \neq 0, \ldots, S_{2 k} \neq 0\right\}
$$

For a symmetric random walk, by problems I.5.8 and I.9.3, we have

$$
\mathrm{E} \mathscr{R}_{N}=1+\sum_{k=1}^{[N / 2]} 2^{-2 k} C_{2 k}^{k} \sim \sqrt{\frac{2 N}{\pi}}
$$

Due to problem II. 10.3, the almost sure convergence is valid:

$$
\frac{\mathscr{R}_{N}}{N} \rightarrow \mathrm{P}\left\{S_{n} \neq 0, n \geqslant 0\right\}
$$