Random walk

For a simple random walk $S$ with $S_{0} = 0$ and $p = 1-q < \frac{1}{2}$, show that the maximum $M = \max \left\{ S_{n}: n \geq 0\right\}$ satisfies $\mathbb {P}\left(M \geq r\right) = (p / q)^{r}$ for $r \geq 0$.

Use generating functions to show that, for a symmetric random walk,

A particle performs a random walk on the corners of the square $A B C D$. At each step, the probability of moving from corner $c$ to corner $d$ equals $\rho_{c d}$, where

and $\alpha , \beta > 0, \alpha +\beta = 1$. Let $G_{\mathrm{A}}(s)$ be the generating function of the sequence $\left(p_{\mathrm{AA}}(n): n \geq 0\right)$, where $p_{\mathrm{AA}}(n)$ is the probability that the particle is at A after $n$ steps, having started at A. Show that

Hence find the probability generating function of the time of the first return to A.

A particle performs a symmetric random walk in two dimensions starting at the origin: each step is of unit length and has equal probability $\frac{1}{4}$ of being northwards, southwards, eastwards, or westwards. The particle first reaches the line $x+y = m$ at the point $(X, Y)$ and at the time $T$. Find the probability generating functions of $T$ and $X-Y$, and state where they converge.

Derive the arc sine law for sojourn times, Theorem (3.10.21), using generating functions. That is to say, let $L_{2 n}$ be the length of time spent (up to time $2 n$) by a simple symmetric random walk to the right of its starting point. Show that

Let $\left\{ S_{n}: n \geq 0\right\}$ be a simple symmetric random walk with $S_{0} = 0$, and let $T = \min \left\{ n > 0 : S_{n} = 0\right\}$. Show that

Let $S_{n} = \sum_{r = 0}^{n} X_{r}$ be a left-continuous random walk on the integers with a retaining barrier at zero. More specifically, we assume that the $X_{r}$ are identically distributed integer-valued random variables with $X_{1} \geq -1, \mathbb {P}\left(X_{1} = 0\right) \neq 0$, and

Show that the distribution of $S_{0}$ may be chosen in such a way that $\mathbb {E}\left[z^{S_{n}}\right] = \mathbb {E}\left[z^{S_{0}}\right]$ for all $n$, if and only if $\mathbb {E}\left[X_{1}\right] < 0$, and in this case

Consider a simple random walk starting at 0 in which each step is to the right with probability $p( = 1-q)$. Let $T_{b}$ be the number of steps until the walk first reaches $b$ where $b > 0$. Show that $\mathbb {E}\left[T_{b} \mid T_{b} < \infty \right] = b /\left|p-q\right|$.

Let $S = \left\{ S_{k}: k = 0,1,2, \ldots \right\}$ be a simple random walk on the non-negative integers, with $S_{0} = i$ and an absorbing barrier at 0. A typical jump $X$ has mass function $\mathbb {P}\left(X = 1\right) = p$ and $\mathbb {P}\left(X = -1\right) = q = 1-p$, where $p \in \left(\frac{1}{2}, 1\right)$. Let $H$ be the event that the walk is ultimately absorbed at 0. Show that, conditional on $H$, the walk has the same distribution as a simple random walk $W = \left\{ W_{k}: k = 0,1,2, \ldots \right\}$ for which a typical jump $Y$ satisfies $\mathbb {P}\left(Y = 1\right) = q$, $\mathbb {P}\left(Y = -1\right) = p$.