# Questions tagged [random-walk]

For questions on random walks, a mathematical formalization of a path that consists of a succession of random steps.

1,427 questions
1answer
25 views

### What is the probability that a random walk starting at 0 will reach +2 in 2 steps, 3 step, 4 steps, etc.? [duplicate]

The random walk I am referring to is a symmetric, unbiased, 1D random walk. In an answer given in the link below, the probabilities are given for S1, but I am trying to find out what it is for S2, ...
0answers
38 views

### How easy is it to create false evidence for a biased coin?

I have a biased coin which comes up heads with probability $p$. I know the value of $p$, but I want to falsely claim that the coin has a different probability of heads, $q$, where $q > p$. To ...
1answer
35 views
+100

### Best way to visualize queueing theory for a Lecture on Markov Chains

Let the Markov Chain $X:=(X_{n})_{n \in \mathbb N_{0}}$ denote, for every $X_{n}$, the number of people waiting in a line at time $n$. Now note that $X$ is a Markov Chain living on $\mathbb Z_{+}$. ...
3answers
18 views

### Getting permutations of independent sequences with uniform probability

Let's say we have $n=3$ sequences noted $A, B, C$ each composed of $m=3$ ordered operations such that $A = (A_0, A_1, A_2)$, $B = (B_0, B_1, B_2)$ and $C = (C_0, C_1, C_2)$. I am searching for an ...
0answers
40 views

### Is there a deeper reason why the simple symmetric random walk on $\Bbb Z^D$ turns transient when increasing $D$ from 2 to 3?

Polya proved the following very well-known Theorem: A simple random walk on $\Bbb Z^D$ is recurrent if and only if it is symmetric and $D\le2$. Dropping simplicity (i.e. allowing jumps to non-...
0answers
18 views

1answer
75 views

### Prove that every position is equally as likely in this random walk scenario

There are two points $A$ and $B$. You are standing in the middle between them. In each step, go half the way to the point $A$, or half the way to the point $B$, each with probability of $0.5$. Mark ...
0answers
46 views

1answer
1k views

### Simple Probability Matrix

Question: Consider a simple model that predicts whether you pass your next test or not based on the result of your previous test. If you pass your previous test, then you have 0.2 chance you will ...
0answers
62 views

### Drunkard’s walk Markov chain

Consider the Drunkard’s walk Markov chain with state space $X =${$0, 1, . . . , N$} and transition matrix: where $0 < α < 1$ is the probability of moving one step from position $k$ to position ...
0answers
16 views

### Reference/suggestion needed - Hitting time of domain equal everywhere -> {domain = sphere, x0 = centre}

So, given a Brownian motion under drift $dX(t) = c dt + dB(t)$ where B(t) is a std Brownian process. Let the process start within some (convex, etc) domain $A$, i.e. $x_0\in A$. Does the following ...
0answers
42 views

### Random walks in triangular and hexagonal lattices

I'm trying to show that the random walk on the triangular and hexagonal lattices in the plane is recurrent, but I'm struggling to find a theorem I could use to prove this, and how to proceed in ...
0answers
12 views

### Upper bound on the number of fixed length, self avoiding paths between two points on a 2D grid

Given some point $x$ on the 2D grid $\mathbb{Z}^2$, is there an upper bound on the number of self avoiding walks of length $n$ between the origin and this point? I have looked at some literature on ...
1answer
21 views

### Stationary distribution of “almost” a random walk

Consider a random walk on $\{1,2,\dots,N\}$, that in state $i$ has probability $p_i$ of going left/right and probability $1-2p_i$ of staying in place, so the transition matrix is \begin{align*} \...
0answers
26 views

### Maximum of a zero-mean random walk

Assume $S_n=\sum_{k=1}^n X_k$ where $X_k$ is i.i.d distributed and $\mathbb{E}X_1=0$ and $\mathbb EX_1^2<\infty$. Let $M_n=\max_{1\leq k \leq n}\{S_k\}$. What is the exponential asymptotic ...
0answers
21 views

### MATLAB - Least Squares Fitting for Log - Log Data to find p value.

This is part of the code for a random-walk simulation. To test the code, I'm using steps=; there will be more values, but I want to run it for 1 trial to decrease code processing. ...
0answers
8 views

### MonteCarlo Random Walk Simulation - steps should be scaled by tmp ? (MATLAB)

I have a question regarding this code snippet that we changed for project 3 Monte-Carlo & Random Walk. monte-carlo-code-segment The code was changed to process all the stepNs. it loops through a ...
1answer
34 views

### Random Walk leaves the compact set about $0$

Let $(X_{k})_{k}$ be IID random variables on $(\Omega, \mathcal{F}, P)$ where $0 < \mathbb E[|X_{1}|]<\infty$ and $S_{n}:=\sum_{k=1}^{n}X_{k}$ Show that $(S_{n})_{n}$ leaves the compact set ...
0answers
21 views

### Chance of not finding an alternating Hamiltonian path in a colored graph in $n$ random walks

Introduction Given a random graph which can be constructed as follows: generate $s$ pairs of unconnected black edges and $2 \cdot s$ vertices connect these black edges using red edges, where the ...
0answers
45 views

### How to calculate a number of all possible random walks without self-intersections?

Is there a certain formula, that gives number of all possible non-self-intersected N walks? N is number of steps of the walk. ...
1answer
823 views

### Probability of completing a self-avoiding chessboard tour

Someone asked a question about self-avoiding random walks, and it made me think of the following: Consider a piece that starts at a corner of an ordinary $8 \times 8$ chessboard. At each turn, it ...
1answer
62 views

### Expected number of visits to $k$ before hitting 0

This problem is from Exercise 5.5.6 in Durrett's Probability: Theory and Examples, 5/E, Use Theorems 5.5.7 and 5.5.9 to show that for simple random walk on $\mathbb{Z}$, if we start from $k$ the ...
1answer
34 views

### Probability of random walk in a specific point - 2D Random Walk -

I've written a simulation in matlab of a 2-D random walk that, at any point, has an equal probability of going to any of the adjacent points. The simulation was run for 10,000 steps on a grid with ...
1answer
22 views

### Conditional Probability and Conditional Independence in Random Walk

A robot randomly walks backward and forward, with probability $p$ and $1-p$ respectively. Let $S_i$ denote the direction he walks on the $i$-th step. Are $S_1$ and $S_2$ independent? What assumptions ...
0answers
9 views

### Simulating a continuous-time, discrete-state Markov chain in fixed time step

To simulate a continuous-time, discrete-state Markov chain with known transition probabilities, we can generate exponentially-distributed waiting time according to current total transition rate, and ...
1answer
25 views

### 1D Random walk with reflective barriers — average time to return to origin

I have very limited probability background, but I came across a problem in an engineering application: Is there a formula that computes the average number of steps taken for a particle beginning at ...
1answer
103 views

### A probability concerning the maximum and minimum of a simple random walk

Let $X_i$ be i.i.d. such that $\mathbb P(X_i = 1 )=\mathbb P(X_i=-1) =\frac1 2$. Let $a\in \{1,2,....\}$, now define the random walk, $S_0=a$ and $$S_n = a+\sum_{i=1}^n X_i$$ Now define the maximum ...
1answer
37 views

1answer
48 views

0answers
24 views

1answer
26 views

### Expected value of random walk with optional stopping

I want to compute the expected value of the following game. I have a symmetric 1-D random walk, I can choose to stop at any time and my winnings will be the value of the random walk. What is the value ...
2answers
238 views

### Exponential ergodicity of biased random walk confined to the positive integer quadrant

I am looking at a discrete-time random walk on $(\mathbb{Z}^{+})^n$, where $\mathbb{Z}^{+}:=\{0,1,2,\dots\}$ and $n\in\mathbb{N}$. At any time, the random walk chooses a uniformly random co-ordinate ...