Articles of random walk

Random walk problem in the plane

Let a particle in the plane $R^2$ executes random jumps at discrete times $t= 1, 2, …$. At each step, the particle jumps from the point it is a distance of lenght one. The angle of any new jump (say, with the $x$ axis) is uniformly distributed in $[0,2\pi]$. Question: If initially ($t=0$) the particle […]

Bounded random walk on one side only: Are you guaranteed to hit the bound?

Let’s say you have a one dimensional random walk, for example integers from 0 to infinity on the number line, and you start at some value $n$ with a probability $P(0)$ to take a step towards zero and a probability $P(\infty)$ to move towards infinity. My intuition tells me that no matter how small $P(0)$ […]

What are some martingales for asymmetric random walks?

Here are some examples for symmetric ones: Is there a similar list for asymmmetric random walks?

Showing that lim sup of sum of iid binary variables $X_i$ with $P = P = 1/2$ is a.s. infinite

Let $(X_i)_{i\in\mathbb{N}}$ be an i.i.d. sequence of binary random variables with $$P[X_i = 1]=P[X_i = -1] = \frac{1}{2}$$ and let $$S_n = \sum_{i=1}^{n} X_i.$$ I’d like to show that $$P[\lim \sup_{n \rightarrow \infty} S_n = \infty] = 1$$ with the means of basic probability theory and the Borel–Cantelli lemma or Kolmogorov’s 0-1 law. Could somebody […]

Null-recurrence of a random walk

In a random walk on $\mathbb{Z}$ starting at $0$, with probability 1/3 we go +2, with probability 2/3 we go -1. Please prove that all states in this Markov Chain are null-recurrent. Thoughts: it is clear all states are inter-communicating, all with periodicity 3, therefore proving state 0 is null-recurrent is enough. null-recurrence One lengthy […]

Modified gambler's ruin problem: quit when going bankruptcy or losing $k$ dollars in all

In each round, the gambler either wins and earns 1 dollar, or loses 1 dollar. The winning probability in each round is $p<1/2$. The gambler initially has $a$ dollars. He quits the game when he has no money, or he has lost $k>a$ rounds in all by this time, no matter how many rounds he […]

Recurrence for random walk

I have the following recurrence which I get when trying to solve a random walk problem given a positive integer $x$. $p_i = \dfrac{p_{i-1}}{2} + \dfrac{p_{i+2}}{2}$ if $0< i < x$ $p_i = 1$ if $i \geq x$ $p_0 = \dfrac{p_{2}}{2}$ I would like to solve this for any integer $0\leq i \leq x$. This […]

Maximum of *Absolute Value* of a Random Walk

Suppose that $S_{n}$ is a simple random walk started from $S_{0}=0$. Denote $M_{n}^{*}$ to be the maximum absolute value of the walk in the first $n$ steps, i.e., $M_{n}^{*}=\max_{k\leq n}\left|S_{k}\right|$. What is the expected value of $M_{n}^{*}$? Or perhaps a bit easier, asymptotically, what is $\lim_{n\to\infty}M_{n}^{*}/\sqrt{n}$? This question relates to, but I need to […]

How long until everyone has been in the lead?

Earlier, I asked a question about a series of competitions: 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. Now […]

What are the assumptions for applying Wald's equation with a stopping time

I am trying to understand the assumptions under which I am allowed to apply Wald’s equation for a sum of a random number $N$ of random variables $X_n$, $1\leq n\leq N$. There seem to be several versions of Wald’s equation, and I am interested in the case where $N$ is a stopping time and the […]