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
17 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}=\frac{1}{2}$ on all edges (x,y), and so the ...
0
votes
1answer
26 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
16 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
9 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 ...
1
vote
1answer
21 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
1answer
36 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 ...
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
40 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
19 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 ...
1
vote
0answers
29 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 ...
2
votes
1answer
79 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
11 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 ...
0
votes
1answer
22 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 $ ...
1
vote
0answers
20 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 ...
0
votes
1answer
17 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 ...
0
votes
0answers
26 views

Origin-seeking random walk

A random walker can choose the distance of each step but not the direction, which is continuous in q dimensions. The walker, who can initially be anywhere in q-space, wants to get ever-closer to the ...
1
vote
1answer
21 views

Computing $E(T_b^2)$ for asymmetric random walk

Let $S$ be an asymmetric random walk with $p=P(X_1=1)>1/2$. Define $T_b=\inf\{n:S_n=b\}$. Prove that $\text{var}(T_b)=\frac{4bpq}{(p-q)^3}$ where $q=1-p$. We know $$\text{var}(T_b)=ET_b^2-(ET_b)^...
2
votes
1answer
25 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 ...
-1
votes
0answers
13 views

Devise a strategy to get out of finite spaced random walk

Can there be a strategy to come out of 2-d finite spaced random walk in finite steps? (i.e. with probability 1)
0
votes
0answers
14 views

Mathematical concept of time series modeling

I am trying to learn about time series (self learner), and I read about the mathematical (or statistical) concept behind analysing time series, however I am still confused about some notions. The ...
1
vote
0answers
9 views

2D Random Walk: Creating Closed Loops

I was wondering if there are any papers out there that study the following 2D random walk situation: 1) Start a random walk at the origin 2) Once the walk forms a loop, stop the walk and "remove the ...
1
vote
0answers
20 views

Using the upper bound lemma, show that $\|Q-U\|\geq\frac{1}{2|G|}\sum^*d_{\rho}Tr(\hat{Q}(\rho)\hat{Q}(\rho)^*)$

Using the upper bound lemma: Let $Q$ be a probability on the finite group $G$. Then, $\|Q-U\|^2\leq\frac{1}{4}\sum^*d_{\rho}Tr(\hat{Q}(\rho)\hat{Q}(\rho)^*)$ where the sum is over all non-trivial ...
1
vote
0answers
26 views

Let $G$ be a finite group and define a probability $P$ on $G$ by $P(id)=1-\frac{\epsilon}{2}, P(s)=\frac{\epsilon}{2(|G|-1)},0\leq\epsilon\leq2$

Let $G$ be a finite group and define a probability $P$ on $G$ by $$P(id)=1-\frac{\epsilon}{2}, P(s)=\frac{\epsilon}{2(|G|-1)},0\leq\epsilon\leq2$$ Show that $P^{*k}(id)=\frac{1}{|G|}+\frac{|G|-1}{|G|}\...
0
votes
1answer
55 views

Brownian Motion problem 22

For a standard Brownian motion $\{W_t, t\geq 0\}$, find $\mathbb{P}(\max_{ t \in [0,1]}|W_t| <x)$. Page 79-80 of Billingsley, P., Convergence of probability measures, New York-London-Sydney-...
0
votes
0answers
16 views

Sampling 1-dim random walk $\{x_k\}_{k=0}^T$ which satisfies $x_0=x_T=0$

Let us consider a moving point $x_k\in \mathbb{R}$, motion of which follows a gaussian random walk: \begin{equation} x_{k+1} = x_{k} + w_k,\;\;w_{k}\sim\mathcal{N}(0, \sigma). \end{equation} What I ...
1
vote
1answer
29 views

Probability of a Large Brownian Particle being at a Certain Position at a Certain Time

I am currently trying to follow along with my notes from a lecture and I am getting very lost in my professor's solution for determining the probability a Brownian particle sits at a specific position ...
0
votes
0answers
33 views

Random walk probability question.

Consider two simple random walk processes, i.e. we have $\{S_{n}' = X_{1}' + \dots + X_{n}'\}$ and $\{ S_{n}' = X_{1} + \dots + X_{n}\}$ on $\mathbb{Z}^d$ ($ \mathbb{P}(X_{i} = e_k) = \mathbb{P}(X_{i}...
0
votes
1answer
20 views

comparison of first hitting times re: discrete, symmetric random walk on $\mathbb{Z}$

Let $c, d \in \mathbb{Z}$ be such that $c < 0 < d$. Let $\tau_k = \inf_{n \geq 0} \left\{n: S_n = k\right\}$ be the first hitting time of state $k$, where $S_n$ denotes the position of a ...
1
vote
0answers
26 views

Number of right jumps of random walk (with possibility of inaction) before hitting time

Suppose we have the random walk $S_t=\sum\limits_{i=1}^t X_i$, where $$X_i = \begin{cases} -1 & \text{with probability } p \\ 0 & \text{with probability } q \\ 1 & \text{with probability } ...
5
votes
1answer
64 views

Transient random walk on 3-color 3-regular tree

Suppose that $T=(V,E)$ is a 3-regular tree with root $0$. Suppose that $0$ is colored green. All other vertices are colored blue, red or green, such that each vertex has exactly one neighbour of each ...
0
votes
1answer
23 views

Escape speed of random walk on positive integers

Let $\{X_i\}$ be the process with transition matrix $$ p(X_{i + 1} = \ell | X_{i} = k) = \begin{cases} q & \ell = k + 1 \quad \text{and} \quad k > 0 \\ 1 - q & \ell = k - 1 \quad \text{and} ...
0
votes
0answers
14 views

Is an exponential function of a stochastic process a smooth function?

Let's say I have an Ito process $X_t$, and another process $Y_t=e^{\int_t^{t+\delta} X_s ds}$. I want to know that quadratic variation of $Y_t$ and another process. I know that the quadratic ...
0
votes
0answers
19 views

Random walks-heavy tailed case

Let $\beta > 0$ and $S_{0}=0$, and let $S_{n}=\xi_{1}+\dots+\xi_{n}$,$n \geq 1$, be a random walk with i.i.d. increments $\{\xi_{n}\}$ having a common distribution $P(\xi_{1}=-1)=1-C_{\beta}$ and $...
1
vote
0answers
15 views

Laplace transform of inverse power law: $t^{-(1+\beta)}$ for $t > 0$ and $0 < \beta < 1$

I came across a paper writing about continuous-time random walk, which derived the number of distinct sites visited by a random walker. It says that given the waiting time distribution $\psi(t) \sim t^...
0
votes
0answers
17 views

Escaping probability for a poisson random walk

Poisson random walk: Let independent random variables $Z_i \sim Pois(\lambda)$. Consider random walk $ S_n = \sum_{i=1}^{n}X_i, $ where $$ X_i = \begin{cases} Z_i &\text{w.p}\; p\\ -Z_i &\...
0
votes
0answers
15 views

How to proceed for finding the first hitting time of such a stochastic process?

A bird can fly and walk on the ground. It has to reach a certain destination. When it flies it has a certain PDF given as: $$P_{fly}(x,y,t)$$ where 2-D motion (x,y) is considered and $t$ is time. On ...
1
vote
1answer
40 views

Probability estimation question.

Consider a random walk with initial point zero. So we have $S_{n} = X_{1} + \dots + X_n$. And we have two fixed numbers $b > 0 > a$. Now we want to show that $(*) = \operatorname{P}(\{\forall n :...
0
votes
0answers
23 views

The probability of seeing a vertex $v_j$ in less than $K$ steps from another vertex $v_i$

I want to calculate the probability of seeing vertex $v_j$ in a random walk in less than $K$ steps from vertex $v_i$ for every pair of vertices. Is there any approach for this problem in polynomial ...
4
votes
2answers
78 views

Bounded 3 values random walk

I have an array of size M, for each shift one random variable $X_i$ enter and one exit. The $X_i$ r.v. are iid and $X_i = \pm1$ with $p=\frac{1}{2}$. Assuming that the sum of the $M$ $X_i$ random ...
0
votes
0answers
9 views

Ordinal scrambling quantification upon placing and retrieving labeled spheres to and from a cylindrical container.

Trying to derive a formula to quantify the degree to which objects in an original order are scrambled upon some amount of repeated random handling. Say there are $n$ spheres labeled with labels $1$ ...
1
vote
1answer
27 views

Random Walk: Proving that $1 = \sum_{m=0}^{n}P_0(S_{n-m} = 0)P_0(\tau_0 > m)$

I would appreciate a further hint for this question: Let $S_n$ a random walk on $\mathbb Z$, with $S_0=0$. Let $\tau_0 = \inf\{n>0:S_n=0\}$, the hitting time of $0$. Show that $$ 1 = \sum_{m=0}...
12
votes
1answer
204 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 ...
5
votes
1answer
68 views

Expected distance squared of random walk on an infinite hexagonal grid

I had a probability test and that was one of the questions: We have an infinite grid of hexagons like this: Each edge have length 1 and all the degrees are 120°. There's a particle in one of the ...
-1
votes
1answer
22 views

Limit of a Symmetric Random Walk

I'm given a probability space of ($\Omega$, $\mathcal{F}$, $\mathbb{P}$) and am asked to look into a symmetric random walk with its n-step defined as $$ X_k = \Bigg\{ \begin{matrix} 1 & \text{...
1
vote
1answer
38 views

Prove Symmetric Random Walk is a Martingale

I'm given a probability space of ($\Omega$, $\mathcal{F}$, $\mathbb{P}$) and am asked to look into a symmetric random walk with its n-step defined as $$ X_n = \Bigg\{ \begin{matrix} 1 & \text{...
0
votes
0answers
22 views

Conditional expectation of a bounded harmonic function

Let $G$ be a discrete group. Consider $G^{\mathbb{N}}$, the space of all sequences in $G$ equipped with product $\sigma$-algebra. Let $m:G^{\mathbb{N}} \to G^{\mathbb{N}}$ be the multiplication map ...
0
votes
1answer
27 views

Recurrent random walk using binomial theorem

I wonder if someone can please check if I am on the right lines. I want to show that a random walk with a probability of a right step of $\frac{1}{4}$ is recurrent. I think I might have done ...
0
votes
0answers
15 views

Random walk with accumulation of penalties

Let a random walf with a certain stopping time $T$. Say that step $i$ costs $i$. If we can compute the average value of $T$, what is the correct (non biaised) way to compute the average cost? Le $E(...