Math Problems Vault

Problem 1.11.1

Let $x, n \in \mathbb {N}$ . Then the fraction of paths from $(0,0)$ to $(n, x)$ that do not cross the zero level, out of the total number of paths from $(0,0)$ to $(n, x)$ , equals $\frac{x}{n}$ .

?

Problem 1.11.2

(a)(b)(c)

Let $S_{0} = 0$ .

?

(a)

Prove that for $n \geq 1$ , $b = -n, -(n-1), \ldots , -1, 0, 1, \ldots , n-1, n$ we have

\mathbb {P}\left(S_{2} \cdot S_{4} \cdot \ldots \cdot S_{2n} \neq 0, S_{2n} = 2b\right) = \frac{|b|}{n} \mathbb {P}\left(S_{2n} = 2b\right)

(b)

Prove that

\mathbb {P}\left(S_{2} \cdot S_{4} \cdot \ldots \cdot S_{2n} \neq 0\right) = \frac{1}{2n} \mathbb {E}\left[\left|S_{2n}\right|\right]

(c)

Find the probability that the random walk never returns to $0$ . In other words, find

\lim _{n \rightarrow \infty } \mathbb {P}\left(S_{2} \neq 0, \ldots , S_{2 n} \neq 0\right)

Problem 1.11.3

Let $\left(S_{n} ; n \in \mathbb {N}\right)$ be a symmetric random walk on the line. Using the reflection principle, prove that

\mathbb {P}\left(\max _{k \leq n} S_{k} \geq N ; S_{n}<N\right) = \mathbb {P}\left(S_{n}>N\right)

?

Problem 1.11.4

(a)(b)

Let $\left(S_{n} ; n \in \mathbb {N}\right)$ be a symmetric random walk on the line.

?

(a)

Find the distribution¹ of the random variable $M_{n}=\max_{k \leq n} S_{k}$ ;

Finding the distribution of a random variable $X$ means finding some exhaustive characteristic of the distribution. For example, the distribution function $F$ or the survival function $S$ $(S(x) = 1 - F(x) = \mathbb {P}\left(X > x\right))$ . In the case of a discrete distribution on some at-most-countable set $B$ , a characteristic of the distribution is the probability function $p(x) = \mathbb {P}\left(X = x\right), \; x \in B$ . An absolutely continuous distribution can be characterized by its density.

The distribution can also be uniquely specified by its characteristic function (Fourier transform).

When asked to find the distribution, it suffices to provide one of the functions listed above, whichever is easier to find. ↩

(b)

Find the asymptotics of $\mathbb {E}\left[M_n\right]$ as $n \rightarrow \infty$ .

Problem 1.11.5

Let $\left(S_{n} ; n \in \mathbb {N}\right)$ be a random walk with probability $p$ of stepping right and $q$ of stepping left, $p+q=1$ . Prove that for $m \leq N$ we have

\mathbb {P}\left(\max _{k \leq n} S_{k} \geq N ; S_{n}=m\right) = C_{n}^{u} p^{v} q^{n-v}

where $v=\frac{n+m}{2}, u=v-N$ .

?

Problem 1.11.6

Let $\left(S_{n}, n \in \mathbb {N}\right)$ be a symmetric random walk on the line. Prove the equality

\mathbb {P}\left(\max _{k \leq n} S_{k}=N ; S_{n}=m\right)=\mathbb {P}\left(S_{n}=2 N-m\right)-\mathbb {P}\left(S_{n}=2 N-m+2\right)

?

Problem 1.11.7

Let the random walk $S_{n}=\sum_{i=1}^{n} \xi_{i}$ , where $\xi_{i}, i=1, \ldots , n$ , are jointly independent and $\mathbb {P}\left(\xi_{i}=a\right)=p, \mathbb {P}\left(\xi_{i}=-b\right)=1-p, a, b \in \mathbb {N}$ . Find $\mathbb {P}\left(S_{n}=x\right)$ .

?

Problem 1.11.8

Let $\xi_{1}, \xi_{2}, \ldots$ be a sequence of independent identically distributed random variables with distribution function $F(x)=\left(1-\frac{1}{x+1} e^{-x}\right) \cdot I\left\{ x>0\right\}$ . Show that

\mathbb {P}\left(\varlimsup _{n \rightarrow \infty } \frac{\xi _{n}}{\ln n}=1\right)=1

?

Problem 1.11.9

Let $\xi_{1}, \xi_{2}, \ldots$ be a sequence of independent identically distributed random variables, $\xi_{i} \sim \mathcal{N}(0,1)$ . Show that

\mathbb {P}\left(\varlimsup _{n \rightarrow \infty } \frac{\xi _{n}}{\sqrt{2 \ln n}}=1\right)=1

?

Problem 1.11.10

Let $\xi_{1}, \xi_{2}, \ldots$ be a sequence of independent identically distributed random variables, $\xi_{i} \sim \operatorname {Pois}(\lambda ), \lambda >$ 0. Show that, regardless of $\lambda$ ,

\mathbb {P}\left(\varlimsup _{n \rightarrow \infty } \frac{\xi _{n} \ln \ln n}{\ln n}=1\right)=1

?

Footnotes