# 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
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, ...
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 ...
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_{+}$. ...
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 ...
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-...
18 views

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 ...
46 views

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 ...
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 ...
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 ...
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 ...
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 ...
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*} \...
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 ...
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=[30]; there will be more values, but I want to run it for 1 trial to decrease code processing. ...
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 ...
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 ...
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 ...
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. ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
37 views

48 views

24 views

Suppose that we have a stochastic process $X(t)$: $$X(t) = \frac{1}{t}\int_{0}^{t} W(\tau) d\tau$$ where $W(\tau)$ is a Wiener process. What is the probability of $X(t)$ crossing a barrier $\alpha$ ($\... 0answers 26 views ### What is the expected number of steps that a random walker needs to reach a place with high probability in a 2D lattice? Let$L_{m,m}$be a$2D$lattice. Also, suppose that there is a random walker located in position$(0,0)$. The random walker goes right, left, up, or down randomly in each step and cannot get out of$...
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 ...