Articles of random walk

Cover Time for Random Walk on a cycle

I’m trying to find the expected time to cover all $N$ nodes on an undirected cycle graph, starting from a given node $k$. The probabilities of moving clockwise and anticlockwise are $\frac{1}{2}$ each. Could you direct me to some entry-level texts/resources which would explain this problem?

Martingales of random walk

Let $S_n$ be a random walk process defined by $$S_n=X_1+\dots+X_n$$ with $X_i \sim N(\mu,\sigma^2)$ and $X_i$ are i.i.d. I’m trying to prove that the quantity $(S_n-n\mu)^2-n\sigma^2$ is a martingale, that is: $$\Bbb E \bigl[( S_{n+1}-(n+1)\mu)^2-(n+1)\sigma^2 \mid \mathcal{F_{t}} \bigr]=(S_{n}-n\mu)^2-n\sigma^2$$ where $\mathcal{F_{t}}$ is the sigma-algebra generated by $(X_1,\dots,X_n)$. My strategy is based on the extension of another […]

Visits from a transient random walker on the integers

Consider a random walk $\{S_n\}$ on $\mathbb{Z}$ with forward probability $p>\frac12$. It is known for such a transient RW that each site is a.s. visited only finitely many times. However, is it true that $$P[\text{Each site to the right of the origin is visited less than }k\text{ times}]=0$$ for all $k>1$? Intuitively, it seems obvious. […]

Probability, that a sequence of $n$ coin-flips contains $k$ changes of the lead

A fair coin is flipped $n$ times. What is the probability $p_k$, that the lead between “heads” and “tails” changes exactly $k$ times ? For example, the sequence $$HHTTTHH$$ contains two changes because “heads” leads at the beginning, after $HHTTT$ , “tails” is in the lead and at the end, “heads” has the lead. A […]

Definition: transient random walk

What exactly does a “transient random walk on a graph/binary tree” mean? Does it mean that we never return to the origin (assuming there is one as for the tree) or just any vertex of the graph or tree? Thanks.

Random walk, Cat and mouse

Here is the problem. In graph G, on different vertices there is cat and mouse. Cat and mouse do independent random walk, but time is synchronous, in one unit of time both cat and mouse do one step. a)Estimate expected life duration of mouse, if cat eat mouse whenever they are on the same vertices. […]

The probability of a “double supremum” of random variable

Let $X_1,X_2,X_3,\ldots$ be IID r.v. with \begin{equation} P(X_i<-1)=0 \end{equation} \begin{equation} P(X_i<0)>0 \end{equation} \begin{equation} P(X_i>0)>0. \end{equation} Define \begin{equation} F_t = \prod_{i=1}^t(1+\frac{1}{2}X_i) \end{equation} \begin{equation} G_t = \prod_{i=1}^t(1+\frac{1}{4}X_i). \end{equation} How can we show, for some integer $S>0$, that \begin{equation} P\left(\sup_{s\in[1,S]} \left[\sup_{t\in[1,s]} \frac{F_t-F_s}{F_t}\right] > \frac{1}{3}\right) > P\left(\sup_{s\in[1,S]} \left[\sup_{t\in[1,s]} \frac{G_t-G_s}{G_t}\right] > \frac{1}{3}\right) \end{equation} Thanks in advance for any hints to […]

Does this modified random walk (2D) return with probability 1?

Pólya showed that a random walk (with the directions at each step uniformly distributed) on the integer lattice returns with probability 1. What if instead we consider the random walk where we are not allowed to go backwards? That is we start at (0,0) and facing “north”, at each step we either turn left, stay […]

First player to win k matches

A series of matches are held between n identical competitors. Each is won by one of the n with equal probability (no ties). I’m looking for a probabilistic description of the outcome when looking at the first player to win 1, 2, … matches. For example, if player #3 is the first player to win […]

A question on calculating probabilities for the random walk

I am currently working on a high school project revolving around the ‘Cliff Hanger Problem’ taken from ”Fifty Challenging Problems in Probability with Solutions” by Frederick Mosteller. The problem is ‘From where he stands, one step toward the cliff would send the drunken man over the bridge. He takes random steps, either toward or away […]