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

learn more… | top users | synonyms

1
vote
0answers
16 views

Reflection principle for walk possible steps right, left and stay

I need to use reflection principle for one dimensional walk with equaly possible steps right, left and stay. I would like to know if hold a similiar identity to that of question Is there an intuitive ...
0
votes
0answers
28 views

Formula to explain table data.

This is part of an excel spreadsheet and I would like to use a formula instead of a table to calculate steps and probabilities and so forth. It is my understanding that the table below represents the ...
1
vote
1answer
47 views

Probability generating function of some “random walk”

Let $S_n=\sum^n_{r=0}X_r$ be a left-continuous random walk on the integers with a retaining barrier at zero. More specifically, we assume that the $X_r$ are identically distributed integer-valued ...
4
votes
0answers
21 views

Brownian Motion in Confined space, any results?

I am searching for work regarding Brownian motion in a confined space, like a sphere or a cylinder, where the wall will serve as reflection boundary. I am wondering if it is possible to derive results ...
0
votes
0answers
9 views

Is Markov Chain property true for correlated inputs?

I have a finite state machine (FSM). At time $k$, state is $\theta^k$ and input is $x^k$. The next state $\theta^{k+1}$ and output $y^k$ are completely determined by \begin{align} \theta^{k+1} &=...
1
vote
1answer
55 views

Confusion about the average distance traveled on a $1$D random walk

The average absolute distance on a one dimensional random walk is supposed to be $\sqrt{n}$. Where $n$ steps are taken from the origin or $n$ is the time. I don't have an intuitive understanding or ...
1
vote
1answer
55 views

1D random walk probability distribution

I am way more physicist than mathematician and this question arises from experimental physics/engineering. The motivation is dealing with small amount of random discrete shifts between measured ...
0
votes
1answer
26 views

Expectation of infimum of asymmetric 1D random walk greater than -$\infty$

I'm reading Durrett's book on Probability and in the example of the asymmetric 1D random walk with $P(X_1=1)=p>1/2$, when trying to compute the expectation of the hitting time $T_{b}:=\inf\{n: S_n=...
1
vote
0answers
27 views

Random walk with drift

Let $X_1,X_2,...$ be independent and identically distributed $\mathbb{Z}-$valued bounded random variables with mean $a=\mathbf{E}[X_1]$, and let $S_n = X_1+\cdots+ X_n$ be the associated random walk. ...
0
votes
0answers
19 views

What is the distribution of the maximum of scaled Gaussian random walk?

A Gaussian random walk is the sum of standard normal variables $$Z(n) = \sum_{i=1}^n X_i,$$ where $X_i\sim N(0,1)$. What I mean by a scaled Gaussian random walk is the following: $$ U(n) = \frac{Z(n)}{...
1
vote
1answer
16 views

Transition from convolution of PMF's to convolution of power series in a random walk

In the proof that symmetric random walks end up regressing to the origin with probability $1$, I have found this didactic post on-line. In it the following two definitions are given: Probability of ...
0
votes
0answers
24 views

Mean Square Displacement of Alternating Random Walk

Consider a 1D random walk with varying steps: the length of the steps is $A$ a fraction $\gamma$ of the time, and $B$ the rest of the time. If $\gamma = 0$, the mean squared displacement approaches ...
0
votes
1answer
16 views

Generating functions in probability first pass through origin of a symmetric random walk

The proof of the eventual return to zero of a symmetric random walk was given here, but I am not comfortable with generating functions. In this book chapter an intermediate result depends on ...
0
votes
0answers
20 views

Random process with very high rate of convergence

Write down a sequence of random (positive, whole) numbers which are not very large (say within a factor of ten or so) compared to its length. Start anywhere not very far from the end of the sequence (...
0
votes
0answers
19 views

Meaning of $\lfloor nt \rfloor$ in $S_{\lfloor nt \rfloor}$

Let $S_n$ be the position of simple random walk at time $n$, with $n \in \mathbb{N}$. What does $\lfloor nt \rfloor$ mean in $S_{\lfloor nt \rfloor}$ for $0 \leq t \leq 1$? More general, what does ...
2
votes
1answer
37 views

Conditional expected number of visits in symmetric random walk with two absorbing barriers

Consider a symmetric random walk on vertices $\{0,1,2,\ldots,n\}$. Suppose that we are at vertex $1$ initially. At each step, we move left with probability $1/2$ and right with probability $1/2$. We ...
1
vote
0answers
20 views

Conditional probability of a random walk hits position $b$ in $n$ steps

This question comes from my question Modified gambler's ruin problem: quit when going bankruptcy or losing $k$ dollars in all Generally, I know the probability that a random walk hits position $b&...
5
votes
1answer
82 views

Modified gambler's ruin problem: quit when going bankruptcy or losing $k$ dollars in all

In each round, the gambler either wins and earns 1 dollar, or loses 1 dollar. The winning probability in each round is $p<1/2$. The gambler initially has $a$ dollars. He quits the game when he has ...
1
vote
1answer
41 views

Random walk on a connected graph

I am reading a book and I have a problem understanding why a relation holds. Assume that we have a time-homogeneous random walk on a connected graph $G=(V,E)$. For $o\in V$, the roundtrip from $o$ ...
1
vote
0answers
14 views

“Return probability” to origin of a variant of the random walk.

Let $\{\epsilon_t\}_{t\ge0}$ be an iid sequence of random variables and let $\lambda>1$. I am interested in the following process: Let $X_0 = 0$ and $$ X_{t+1} = \lambda(X_t+\epsilon_t). $$ This ...
-1
votes
2answers
49 views

What is the probability of random walking ant to be at a position after some finite steps on an infinite grid? [closed]

Is it even calculable? What if the grid is infinitely dimensional? Lets say that it is a simple random walk, and probability to move to any neighboring position is equal, but other types are also ...
1
vote
0answers
29 views

Area under staircase walk

If I create a random lattice path from $(0,0)$ to $(n,k)$, taking only north or east steps $(1,0)$ or $(0,1)$, with equal probability, the so called staircase walk, what are the moments of the area ...
0
votes
0answers
21 views

Random walk on a segment with infinite time

Given a point particle on a segment $L$ of length $1$, $(L=[0,1])$, assume the particle moving randomly in such a way: $p_{(k+1)}=p_k+\delta_k$ where $p_{k+1}$ is the position on the segment at time $...
1
vote
0answers
26 views

Return probability of a SRW in an even number of steps

I am looking for some references for the following problem. Consider a graph $G$ and a simple continuous time random walk $(X_t)_{t\geqslant 0}$ on this graph. Consider the family of events $(e_t)...
1
vote
1answer
117 views

States of a Group Ring

Let $G$ be a finite group and $\mathbb{C}G$ its group ring. Now taking the approach of orangeskid, consider the space $\mathbb{C}G$ as a Hilbert space with orthonormal basis $\delta^g$. $G$ acts on ...
1
vote
1answer
85 views

Exact Expected Value of Random Walk?

i just read in Noga Alon's Book That the exact expected value of a random walk is which was a question in putnam competition... $\displaystyle{S_{n} = X_{1} + X_{2} + \cdots X_{n}}$. Which $\...
1
vote
2answers
46 views

Probability of $\max_i \{X_i\} = X_0$ where $X_i$ are iid binomial

We have $M$ Binomial random variables, where $X_0 \sim $ Bin$(n,p)$ and $X_i \sim $ Bin$(n,1/2)$. Suppose $p > 1/2$. I'm interested in the probability that $\mathbb{P}(\max \{X_1,\dots,X_M\} \geq ...
0
votes
1answer
19 views

Random walk mean number of visits to state before absorption

This is from Stirzaker's book Random Processes. Suppose we have a simple random walk with probability going "up" p, "down" q. At time 0 it stats at 0, so $$S_0 = 0$$ Now let $u_b $ be the mean ...
0
votes
0answers
18 views

Bernstein-type inequality for simple random walk

Let $(X_n)$ be a sequence of random walks: $P(X_i=1) = P(X_i=-1)=1/2$. Denote $S_n = X_1+...+X_n$. Show that, for $0 < \epsilon \leq 1/4$ $$P\bigg\{\bigg | \frac{S_n}{n} \bigg| \geq \epsilon \bigg\}...
0
votes
1answer
24 views

Continuous random walk

I am reading a book that is talking about continuous random walk. It first starts with defining one dimensional discrete random walk as starting at point 0 and move to either to the right or left at ...
1
vote
1answer
19 views

Compute covariance matrix random walk

Consider a random walk on the square lattice $\mathbb{Z}^2$ with diagonal jumps of size $2$, i.e. the jump probabilities are $$P(X_1 = x) = \begin{cases} \frac{1}{4} & \quad \text{if } ...
1
vote
2answers
48 views

Approximation of probability that the walker is at the origin after $2n$ steps

I'm reading Lawler's "Lecture on comtemporary probability". There are $2$ parts in the book that I don't understand: "In order for the walker to be at the origin after $2n$ steps, the walker will ...
0
votes
1answer
47 views

Three-Dimensional Random Walk

A particle starts at an origin $O$ in three-space. Thinking of point $O$ as the center of a cube 2 units on a side. One move in this walk sends the particle with equal likelihood to one of the eight ...
0
votes
1answer
38 views

Stopping times of random walk with time dependent absorbing barriers

I have a Bern$(p)$ random walk ($Y_i = 1$ with probability $p$ and Y_i = 0 with $1-p$) with two absorbing boundaries, $A: Y^i \leq t_i$ and $B:Y^i \geq d_i-t_i$. Now, both $d_i$ and $t_i$ are evolving ...
0
votes
0answers
22 views

Show that $S_n/n$ converges in probabilty but not almost surely - Borel Cantelli

Let $X_n$ be independent random variables with the following distribution: $$ P(X_n=\pm n)=\frac{1}{2(n+1)\log (n+1)}, \;\;\;\; P(X_n=0)=1-\frac{1}{(n+1)\log (n+1)} $$ and let $S_n=\sum_{k=1}^n X_k$....
2
votes
0answers
27 views

'Finding' a normally distributed random variable

Let a random variable $Z$ have a standard normal distribution. Suppose that we start at $0$. We 'walk' right, along the number line, till we reach $a$. We then turn around, walk back, past $0$, till ...
0
votes
0answers
41 views

Integral of non-Gaussian distribution, random walk?

I would like to evaluate $$ F = \frac{\mathbb{E} \left\{\left(\int_0^T x^3(t) dt \right)^2\right\}}{\mathbb{E} \left\{\left(\int_0^T x(t) dt \right)^2 \right\} } \approx \frac{\mathbb{E} \left\{\left(...
1
vote
3answers
47 views

Probability of reaching net 4 heads when tossing coin 8 times

This problem is #19 from the AMC 12 2016A, and goes as follows: Jerry starts at $0$ on the real number line. He tosses a fair coin $8$ times. When he gets heads, he moves $1$ unit in the positive ...
2
votes
0answers
32 views

joint-probability of Langevin equation

I am working on Langevin equations: $\frac{dx}{dt}=u$ $m\frac{du}{dt}= -\gamma u + \theta(t)$ where $\theta(t)$ is delta-correlated in time Gauss-distributed noise with zero-mean $\langle \theta (...
1
vote
0answers
29 views

The probability that the d-dimensional symetric random walk returns to the origin - is this relatively short proof correct?

Let $p_n$ denote the probability of returning to the origin after n steps. If n is odd, $p_n = 0$. The main insight is that $\sum_{n=0}^{\infty}p_{2n}$ is asymptotically ~ $C \cdot \frac{1}{n^{d/2}}$ ...
3
votes
0answers
48 views

Hitting probabilities in a random walk on a graph

Consider a random walk $(X_n)$ on the graph below, where we jump from a given vertex to one of its adjacent vertices with equal probability. I want to find: the probability that we hit $A$ before ...
2
votes
2answers
29 views

Divergence of asymmetric not-simple random walk

Consider a (not simple) random walk $S_n = \sum_{k=0}^n X_k$ where X_k are i.i.d and the mean $\overline{X}<0$. Is there is simple proof or a reference showing $P( \lim \limits_{k \to \infty} S_k = ...
0
votes
0answers
52 views

Random walk visiting $k$ distinct points

I have a random walk on $\mathbb{Z}$ with starting point $0$ and with length $n$ and possible steps to right, left or stay where you are, all with the same probabilities. I am interested in exact ...
2
votes
1answer
34 views

Expected number of zero crossings in 3 value random walk

Let's say we have a 1D random walk starting at the origin where we go up $1$ with probability $1/5$, down $1$ with probability $1/5$, and stay put with probability $3/5$. If we walk $n$ steps, what's ...
3
votes
0answers
34 views

$2D$ random walk stopping time

A $2D$ random walk starts at $(X_0, Y_0) = (k, k)$ where $k>0$ is an integer. At each step $(X_{n+1}, Y_{n+1}) = (X_{n}-1, Y_{n})$ or $(X_{n+1}, Y_{n+1}) = (X_{n}, Y_{n}-1)$ with the same ...
2
votes
0answers
37 views

Survival probability of a biased random walker

A random walker moves to $+1$ with probability $p$ and moves to $-1$ with probability $q=1-p$. If he starts at point $m$, what is the probability that he doesn't hit the point zero after $k$ steps, ...
0
votes
1answer
21 views

Probability of maximum of a random walk?

Let us consider a random walk denoted by Sn and let Mn be the maximums of the random walk. Now let us consider that this random walk will end at some point k. SO I am stuck how to prove this equality: ...
1
vote
1answer
29 views

Fluctuations in estimator of $\min\{p,1-p\}$

Let $X_1,\ldots,X_n$ be i.i.d. Bernoulli with some parameter $1/2$. Let $\bar{X}_n = \frac{1}{n} \sum_{i=1}^n X_i$. I am trying to show $$\mathbb{E} \min\{\bar{X}_n,1-\bar{X}_n\} \ge \frac{1}{2} - C n^...
3
votes
1answer
40 views

Probability that two random walks on $\mathbb{Z}^2$ meet at the origin

Suppose $X,Y$ are symmetric, independent random walks on the lattice $\mathbb{Z}^2$. I am trying to find the probability: $$\mathbb{P}\big(X_n=Y_n=(0,0)\;\text{for some}\;n\,\big|\,X_0=Y_0=(0,N)\big)$$...
0
votes
0answers
14 views

Gaussian blur over (or random walk in) a surface mesh

Let $V$ be the set of mesh vertices, connected by edges $E$, forming a mesh that represents a surface embedded in $\mathbb{R}^3$. On this mesh a function $f:V\rightarrow\mathbb{R}$ is defined. For ...