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.

0
votes
1answer
38 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 ...
0
votes
0answers
15 views

What does Markov Property Have to do with $P^{x}(X_{n}=x)P^{x}(X_{i}\neq x \operatorname{ for all} i \geq 1)$

I am aware of the Markov Property, i.e. that: $P(X_{n+1}=x_{n+1}|X_{n}=x_{n},...,X_{1}=x_{1})=P(X_{n+1}=x_{n+1}|X_{n}=x_{n})$ But I cannot seem to understand the following: Let $\sigma:=\{k \in \...
4
votes
0answers
45 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
59 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
8 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
0answers
14 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 ...
8
votes
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 ...
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
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*} \...
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
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
votes
1answer
33 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
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 ...
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. ...
0
votes
1answer
33 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 ...
3
votes
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 ...
0
votes
0answers
7 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 ...
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
28 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 ...
0
votes
1answer
33 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)$$
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
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
70 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
23 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
25 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
24 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 ...
1
vote
0answers
9 views

Expectation of fourier exponential

Suppose I have some probability distribution in $\mathbb{R}^n$ and I want to calculate the expectation value of $$\left\langle e^{-i\vec{q}\cdot\vec{r}}\right\rangle^n.$$ My professor says that the ...
0
votes
1answer
20 views

Computing expected minimum of stopping time and n with simple random walk

Let $(S_n)$ be an elementary random walk, ie. $S_n = \sum_{i=1}^n X_i$ where $P(X_i = 1) = P(X_i = -1) = \frac12$. Let $T = \inf \{ n : S_n \in \{-2,2\}\}$. $T$ is clearly a stopping time and is ...
0
votes
0answers
17 views

Is a random walk on an isoradial graph transient?

Is the random walk on an isoradial graph defined in Chelkak and Smirnov (2011) (in pages 3-4) transient? Let us define the random walk on an isoradial graph $\Gamma$ starting from $x$ by, \begin{...
0
votes
1answer
42 views

Showing that $ES_N=0$ for a random walk where $N$ is a stopping time and $EN^{1/2}<\infty$

Question Let $\xi_{1}, \xi_{2}, \dotsc$ be i.i.d random variables with $E \xi_i=0$ and $E\xi_i^2<\infty$. Let $S_n=\sum_{i=1}^n \xi_i$ and $N$ be a stopping time. If $EN^{1/2}<\infty$, then $...
0
votes
0answers
17 views

predicting random walks with eigenvalues

(1 point) 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.6 chance you will ...
1
vote
1answer
37 views

Can we relate the recurrence/transience of a lazy random walk with the recurrence/transience of a non-lazy random walk?

Consider the following discrete-time random walk on $\mathbb Z$: where at location $n\in\mathbb Z$, the walker has probability $q_n$ of taking one step left, probability pn of taking one step right, ...
0
votes
0answers
21 views

Hitting time on linear Markov chain

I came across this problem in a math course of mine a while back, and I haven't been able to solve it since. Anyone have any ideas? Suppose we have a chain of $n$ vertices, such that the first ...
0
votes
1answer
28 views

random experiment with two different functions on unit interval

Let $X=[0,1]$, and functions $f(x)=x$, $g(x)=2x$ mod $1$, and the probability of chosing $f,g$: $\mu(f)=\mu(g)=\frac{1}{2}$. Now if $x$ is the starting point, then what will be a general expression of ...
1
vote
1answer
41 views

Drunk guys in a race, who will win? (random walk)

We initially have M drunk guys located on the x-axis at positions $\mu_1,...,\,u_M$. As they are all completely "wasted", they will just randomly walk around in this 1D space for a while. After a few ...
1
vote
1answer
33 views

Random walk by a monkey

A monkey is sitting on $0$ on $\mathbb{R}$, at $t = 0$ . In every period $t\in({1,2,\dots})$ it moves one unit to the right with probability $p$ and one unit to the left with probability $1-p$. Let $...
0
votes
0answers
28 views

The conductance of a random walk on an undirected graph

Consider a random walk on an undirected graph consisting of an $n$-vertex path with self-loops at the both ends. With the self loops, we have $p_{xy} =1/2$ on all edges $\left(x,y\right)$, and so the ...
0
votes
1answer
32 views

Markov chain: Relation between absorbent states and its eigenvalue.

I'm a computer science student, and I'm really stuck in this lemma since I cant find out anything about the relation between a absorbent state (in a Markov chain $M$, a absorbent state is when the ...
2
votes
0answers
36 views

Fourier transform of a random walk

I was just reading Statistical Field Theory of Itzykson and Drouffe and saw that they wrote the inverse Fourier transform $$P(\vec{x},t,\vec{x}_0,t_0)=\int_{[-\pi,\pi]^d}\frac{\text{d}^d\vec{k}}{(2\pi)...
0
votes
0answers
10 views

n-consecutive beam splitters

I think this problem fits better here rather than the physics stackexchange. This is a problem that has bugged me for a long while, and might be an interesting problem for the math stackexchange. A ...
0
votes
0answers
8 views

Multiple Independent random walks on same digraph

Consider $n$ individuals performing an independent random walk on the same digraph. For simplicity assume that the graph is strongly connected. What can we say regarding the expected number of ...