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
0answers
4 views

Unimodular walks?

I am reading a book on random walks on graphs and I found the following text: "A more general context is that of jump distributions invariant under a transitive unimodular graph automorphism subgroup ...
0
votes
0answers
4 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$ ...
34
votes
1answer
806 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 ...
1
vote
0answers
20 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
21 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
23 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
276 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,...
0
votes
0answers
12 views

what could be a good master thesis topic that relate probability and stats with machine learning or AI? [closed]

I'm doing an mba in statistics, and i'm thinking about an interesting topic to make my thesis. i'm mathematician and would be nice to make something that apply something like chaos theory dynamical ...
1
vote
1answer
47 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
27 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
203 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
52 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
33 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
24 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
22 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 ...
3
votes
2answers
236 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 ...
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
18 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
15 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
25 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 ...
1
vote
1answer
34 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
16 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 ...
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
27 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
40 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 ...
2
votes
3answers
3k views

Exact Probability of Collision of Two Independent Random Walkers After N Steps

Two drunks start together at the origin at $t=0$ and every second they move with equal probability either to the right or to the left, each drunk independently from the other. What is the probability ...
1
vote
1answer
28 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
1answer
31 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 ...
6
votes
2answers
102 views

Equivalence between “gambler's ruin” and seemingly different game

My question concerns two experiments with different rules, but with the same probabilities. I was wondering, is there is an intuitive explanation for this equality, or is it is a coincidence? Suppose ...
1
vote
1answer
27 views

Probability of a random walk with positive drift cross a negative threshold

Assume that $S_i(k) =\sum_{t=1}^k X_i(t)$ for $i = 1,2.$ $X_i(t)$ are i.i.d. random variables with positive mean. What is the probability that $\inf_k \{\max_{i} S_i(k)\}< -a$, for some a > 0? I ...
2
votes
0answers
24 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 ...
2
votes
1answer
41 views

Crossing time(meeting time) of a gaussain random walk

Assume $\{S_n\}_1^\infty$ is a random walk, where $S_n=\sum_{i=1}^n X_i$ and $X\sim N(1,1)$, where N(1,1) is normal distribution with mean 1 variance 1. Define stopping time when it cross a positive ...
2
votes
1answer
83 views

The property that there exists an $r \in (0, 1)$ such that $P(Z_n = x) \leq r^n$ for a random walk $(Z_n)_{n \geq 0}$.

If we have a random walk $(Z_n)_{n \geq 0}$, one can ask whether there exists an $r \in (0, 1)$ such that $P(Z_n = x) \leq r^n$ for all $n, x$. Based on my own (possibly wrong) observations, this ...
0
votes
0answers
49 views

Loops in Matlab to solve a random walk problem

The matlab exercise states "Suppose now that you are playing the game with 100 coins (50 coins for each player to start) with a loaded dice such that the probability that the dice rolls to an even ...
1
vote
1answer
41 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_{...
0
votes
2answers
21 views

Under what conditions the gambler's ruin problem may continue indefinitely?

I'v seen the gambler's ruin problem problem on Ross.A book on probability. My question is that under what conditions on the starting money of A and B will the game continue indefinitely? In the book ...
12
votes
1answer
209 views

Random walk on thin ice?

My Question: Is the stochastic process which is described below a (special case of a) well-studied model? What kind of properties are known under which assumptions? Let's think of a random walker on ...
1
vote
0answers
31 views

Simple Random Walk Property

Define $S_n = \Sigma_{i=0}^n X_n$, where $X_n = \pm1$ with probability $1/2$ for each case. I am trying to show that for a walk of length $2n -2k$ starting at $0$, the probability that it does not ...
0
votes
1answer
27 views

Expected number of steps before leaving a ball

Consider an infinite undirected graph $G$, like for example $\mathbb{Z}^d$ with edges connecting nearest neighbours sites. Let $X(t)$ be a simple random walk starting from the origin, $o$, define $ ...
0
votes
0answers
12 views

Cumulative Distribution Function of Sequence Generated via Random Walk

Is it possible to generically describe the CDF of a finite length random sequence generated by storing the trajectory of a random walk? For example, assume $X$ is an iid random variable with the ...
1
vote
0answers
23 views

Asymmetric random walks: eigenvalues and spectral gap

For a reversible finite-state Markov chain, the second largest eigenvalue determines how fast the Markov chain converges to its stationary distribution. A few questions (e.g, 1, 2) refer to Chapter ...
0
votes
0answers
19 views

Comparing Biased Random Walk models

Given a single graph, and two different "biased" random walk models on the same undirected graph, how does on theoretically compare the two models? What are the metrics one should theoretically study ...
2
votes
1answer
32 views

Stopped random walk is not uniformly integrable

I know that in general Doob's Optional Stopping Theorem doesn't hold for unbounded stopping times, but that it does when the system up to the stopping time is uniformly integrable. One counter ...
0
votes
1answer
19 views

Distribution of right jumps conditional of hitting time for a random walk with possibility of inaction.

Suppose we have a random walk that moves in discrete time. It starts at zero and in each period it jumps one unit to the right with probability $\alpha$, it jumps to the left one unit with probability ...