Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [random-walk]

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

2
votes
0answers
10 views

Random Walk $\mathbb P(T_0>n $ and $S_n=a) = \mathbb P(T_a=n) =\frac{a}{n} \mathbb P(S_n=a)$

Consider the random Walk $S_n$ on $\mathbb Z$ starting in $x=0$. Let $a\in \mathbb Z$. Define $T_a(\omega)=\min\{n\in \mathbb N : S_n(\omega)=a\}$. Show for $a> 0$ $\mathbb P(T_0>n $ and $S_n=...
0
votes
2answers
48 views

Calculating $E(2W(s)+W(u)|W(u)=2)$

Let $W(t)$ be standard Brownian motion and let $u<s$. I know that $W(s)\sim\mathcal{N}(0,\sqrt{s}), W(u)\sim\mathcal{N}(0,\sqrt{u})$ and $2W(s)+W(u)\sim\mathcal{N}(0,\sqrt{8s+u})$. How should I ...
8
votes
1answer
89 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 ...
0
votes
1answer
26 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, ...
4
votes
0answers
41 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 ...
1
vote
1answer
40 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_{+}$. ...
2
votes
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 ...
2
votes
0answers
41 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-...
2
votes
0answers
20 views

Hitting and excursion times for biased random walk on the hypercube

I consider the following update rule for a random walk $\{X_{t}\}_{t \geq 0}$ on the hypercube $\{0,1\}^{n}$: At each time step, I sample $I \in \{1,2,\ldots,n\}$ uniformly at random and $U \sim ...
0
votes
0answers
9 views

Sample autocorrelation of random walk with drift

I would like to calculate the autocorrelation of a sample whose data generating process is a random walk with drift. I generated the movement over 250 time points of a fictious stock price with ...
6
votes
1answer
691 views

What is the probability a random walk hits x before it hits y?

This problem was motivated by my bitcoin trading and recalling some of my math education back in the day. I thought I'd ask people who know this much better than I... Suppose there is a continuous, ...
2
votes
2answers
53 views

Simple random walk on $\mathbb Z$; Coupling Argument

I am reading the proof of Theorem 3.1 from these notes and I am stuck at one point. Let $X_1, X_2, X_3, ...$ be i.i.d random variable valued in $\{1, -1\}$ each distributed uniformly. Let $S_n=\sum_{...
4
votes
0answers
46 views

Distance from origin of biased random walk conditioned to be positive at time n

Let $S_n$ be the position of a simple random walk on the integers started from $0$ that moves right with probability $p<1/2$. What is the asymptotic behavior of $$E[ S_n \mid S_n >0 ]$$ as $n \...
0
votes
0answers
9 views

Projection of 4D symmetric SRW $S$ is 3D symmetric SRW and $S$ is transient

I would like to know why in the following proof we sum over $k$ and why does $Y_n$ being transient imply $S_n$ is. Let $S_n$ be a four dimensional symmetric SRW with $S_0=0$ and denote with $S_n^*...
0
votes
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 ...
0
votes
0answers
63 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 ...
0
votes
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 ...
1
vote
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 ...
1
vote
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 ...
0
votes
1answer
22 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*} \...
1
vote
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 ...
1
vote
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=[30]; there will be more values, but I want to run it for 1 trial to decrease code processing. ...
0
votes
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 ...
-1
votes
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 ...
1
vote
0answers
22 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 ...
1
vote
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. ...
35
votes
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 ...
3
votes
1answer
63 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 ...
0
votes
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 ...
0
votes
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 ...
0
votes
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 ...
1
vote
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 ...
4
votes
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 ...
1
vote
1answer
37 views

Bounding the cheeger constant of a cover of a graph?

Suppose that $G$ and $H$ are connected graphs, and that $\phi : G \to H$ is a $n$-fold covering. Let $h$ denote the Cheeger constant. I know that $h(G) \leq h(H)$. Question: Is it also the case that $...
1
vote
0answers
16 views

Non-markovian random walks and their applications in machine learning

I'm searching applications of random walks in machine learning. In particular, applications of random walks with long memory. An example of this kind of processes is the so called ELEPHANT RANDOM WALK....
1
vote
0answers
12 views

Conditional expectation for a simple random walk

Suppose that $S_n$ is a simple random walk started at $0$, so that $S_n = X_1 + \dots + X_n$ where $X_j$'s are iid random variables taking values $1$ and $-1$ with probability $p = 3/4$ and $q=1/4$ ...
1
vote
0answers
24 views

Escape time probability distribution

I have a system where a random walker is moving on $\mathbb{Z}$. However, at each point in $\mathbb{Z}$, there is a probability $q$ that an escape route exists along which the walker can escape. I ...
0
votes
0answers
5 views

Estimating the discrete random walk probability by error function

I am trying to work out the asymptotic large $t$ behavior of following function \begin{equation} f(t ) = \sum_{x = 0}^{2t} { 2t \choose t + x} p^{ t+x } (1 - p)^{ t - x} = \sum_{x = 0}^{2t} { 2t \...
0
votes
1answer
30 views

Prove a general random walk is not stationary

Here is my attempt. $X_t$ is a general random walk is when we have a sequence of independent and identically distributed random variables $Y_1,Y_2,...$ such that $X_0=0,$ $X_1=Y_1$, $X_2=Y_1+Y_2$ and ...
1
vote
0answers
25 views

Does the specific sequence of random variables converge almost surely to a given constant?

Suppose, $\{X_n\}_{n = 1}^{\infty}$ is a sequence of i.i.d random variables, such that $P(X_i = 1) = P(X_i = -1) = \frac{1}{2}$. Now, suppose $\{S_n\}_{n = 1}^\infty$ is a sequence of random variables ...
4
votes
2answers
284 views

The problem of the drunkard in a valley.

We consider a Markov chain on a subset of positive integers $S =$ {$0, 1, 2, 3, .......N$}, with transition probabilities defined as follows: The chain jumps only one unit to the left or right. $p(i,...
1
vote
1answer
48 views

Simplifying summation of binomials

I am working on a proof and think that the following equality holds but am unable to prove it: $$ \sum_{k_1=0}^{m} \sum_{k_2=0}^{m-k_1} \dots \sum_{k_{d^2/2}=m-(k_1+k_2+\dots+k_{d^2/2-1})}^{m-(k_1+k_2+...
0
votes
1answer
34 views

Symmetric random walk calculate

In basic, symmetric random walk with $P(Y_{n}=1)=\frac{1}{2}$, $S_{0}=0$, calculate: $$P(S_{1}>0,...,S_{2n-1}>0, S_{2n}=0)$$
13
votes
1answer
206 views

How can I prove this bijection between random walks?

Let $R_n$ be the set of simple random walk paths such that $S_n=0.$ $P_n$ be the set of simple random walk paths such that $\forall i \in \{1,2,...,n\},$ $S_i > 0$. $N_n$ be the set of paths ...
0
votes
0answers
53 views

Who gets the broccoli stick? Random walk in a circle. [duplicate]

Suppose we have $n+1$ people in a circle ${0,1,2,3....n}$, we pass around a broccoli stick. The person $k$ has probability $p$ to pass the stick to $k+1$ and probability $q = 1-p$ to pass it to the $k-...
0
votes
3answers
79 views

2D Random Walk: Average distance after 2 steps

A simulation of 50,000 iterations gives the average distance after a 2-step (unit step) random walk on a 2 dimensional plane, which is around 1.27. But how can one mathematically prove this? Any ...
0
votes
0answers
19 views

Stochastic Processes Formula

I am trying to solve this question on stochastic processes which is to show that for $$I_0=0\\\\ I_n=\sum_{j=0}^{n-1}M_j(M_{j+1}-M_j), \quad n=0,1,2,... $$ the equation can be writen as; $$I_n=\frac{...
2
votes
0answers
24 views

Probability of a stochastic process crossing a boundary in time interval

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$ ($\...
0
votes
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 $...
0
votes
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 ...