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

learn more… | top users | synonyms

2
votes
1answer
48 views

Why is this true with random walks?

Let $S_n=\sum_n{X_n}$ a random walk with $P[X=1]=p=1-P[X=-1]$. Prove that for any $k \in Z$ $P[\cup_{n \geq1} \{S_n\geq k\}]= (P[\cup_{n \geq1} \{S_n\geq 1\}])^k$ I do not understand why is this ...
1
vote
1answer
51 views

Help with a symmetric random walk problems

Given a simple symmetric random walk $X_1,X_2,…,X_n,…$ where $X_t,t=1,2,…$ are i.i.d random variables distributed according to $\Bbb P(X_t=1)=1/2$ and $\Bbb P(X_t=-1)=1/2$. Define partial sum ...
2
votes
0answers
32 views

An inequality for standard random walk.

How to prove that $\Bbb P_1(\lim\sup_{n\to\infty}\frac{\log \bf{x}(n)}{\log n}\le \frac{1}{2})=1$, with the suggestion that $\bf{x}(n)$ goes to $\infty$ like $\sqrt{n}$. Here $\bf{x}_n$ is the ...
1
vote
1answer
80 views

Random walk in a graph

This is a question about random walk from vertex $s$ in a graph (can be directed), which is defined in the following manner: The random variable $X_0$ (whose possible values is the set of vertices) ...
1
vote
0answers
77 views

Wald's Identity for non-i.i.d. Case

I am looking for Wald's Identity for non-i.i.d. case as discussed in the following links: https://en.wikipedia.org/wiki/Wald%27s_equation What are the assumptions for applying Wald's equation ...
3
votes
2answers
47 views

Random Walk UpperBound

enter image description hereIs it possible to prove that for any symmetric Random Walk the absolute value of its partial sum $S_n$ never exceeds $\sqrt{2 \pi n}+\sqrt{\pi / 2}$ ? I run some ...
0
votes
0answers
21 views

Transience of random walks starting from each of the sites which have been already visited

Consider a simple random walk on $\mathbb{Z}^d$, $d \geq 3$, which starts from the origin. As $d \geq 3$, there is a positive probability that the random walk never visits the origin again. Now, let ...
0
votes
0answers
17 views

Discounted stochastic linear regulator problem with a transversality condition: I think I have a solution, need proof

Consider a sequence of i.i.d. random variables $ \left\{ {{\varepsilon _t}}\right\}_{t = 1}^\infty $ with $E\left( {{\varepsilon _t}} \right) = 0 $ and $ E \left( {\varepsilon _t^2} \right) = ...
0
votes
1answer
25 views

Calculating infinite sum from a random walk in 1-dimension

Consider the random walk on $\mathbb{Z}$ with 1-step transition probabilities $p_{i,j} = \frac{1}{2}$ iff $|i - j| = 1$. Then the probability that the first time that the chain returns from $i$ to $i$ ...
1
vote
0answers
15 views

How does one reconcile the fact that a random walk is non-mean reverting with Polyas recurrence theorem?

In particular, Polyas theorem says that in 2 or 1 dimension the symmetric random walk is recurrent so that it has probability 1 of returning to zero. Yet, I have read that random walks are known as ...
3
votes
0answers
30 views

$S_n \in [-a,a]$ for some $a$ infinitely often

Suppose we have iid r.v.s $X_n \in \mathbb{R}$ with mean $0$ variance $\sigma^2$, I wonder is it true that we have $\exists a>0,$ $$P(S_n \in [-a,a] \text{ infinitely often} )=1,$$ where $S_n ...
0
votes
0answers
33 views

Continuation of random walks

I have trouble understanding the following identity: $\mathbb{E}[e^{i\theta\cdot T_t}]=\sum_{j\geq 0}{e^{-t}\frac{t^j}{j!}\mathbb{E}[e^{i\theta\cdot S_j}]}$. I see that somehow it uses the following ...
0
votes
1answer
29 views

What's the difference between a white noise process, IID process and random walk?

Just need some clarification between these concepts. Is an IID with mean zero white noise process? Also is random walk a summation of white noise process?
1
vote
1answer
135 views

What is the relationship between eigenvector and computing PageRank?

I read several papers about PageRank and didn't get stuck in understanding the idea of PageRank because it is simple, but I got stuck in computing PageRank, those papers talk about some mathematical ...
1
vote
0answers
38 views

Symmetric random walk about $y=2$.

Consider a simple (symmetric) random walk $p=q=\frac{1}{2}$ and $(X_n)_{n\geq 0}$ with $X_0 = 0$. Using the reflection principle, find the probability that $X_{12} = -4$ and $X_1 < 2$, $X_2 < ...
2
votes
1answer
65 views

What is a good/extensive undergraduate level reference on random walks?

Random walks on graphs, expected times for different things, gambler's ruin. I seem to either stumble on some pretty advanced texts about group representation theory or texts that briefly mention it ...
1
vote
1answer
56 views

Random walk - Markov chain

I have a problem.If we start at place $0$ and the probability to go right is $p$ and the probability to go left $q$. I need to calculate the probability after 100 steps that the maximum place when we ...
2
votes
1answer
39 views

A Game of Random Walk plus Combinatorics

1 Original and reasons for this game This game is actually changed from Geoffrey and David's Book [1] (section 11.2, page 445) and its accompanying solution manual [2]. The book gives the result ...
0
votes
0answers
44 views

Brownian motion determining probability of success for binomial experiment

Suppose you have some particle that moves according to brownian motion in one dimension (x), in discrete time steps. Suppose you have, for each position x, a probability P(x), which specifies the ...
4
votes
0answers
70 views

Distribution of $\max_{n \ge 0} S_n$, random walk.

Say I have a random walk that's a nearest neighbor random walk on the integers where at each step the probability of moving one step to the right is $p$ and the probability of moving one step to the ...
1
vote
0answers
59 views

Random walk evaluated by a Poisson process

I found the following proposition and I want to prove it. Let $S_n$ be a discrete-time random walk with increment distribution p and $N_t$ be a Poisson process with parameter $1$.Then the process ...
0
votes
0answers
32 views

Random walk in $1$ dimension with non-equal left and right probabilty

Consider a typical random walk problem, where the probability to go right is $R$ and the probability to go left is $L$, where $R+L=1$. The particle can move 1 unit in each step, and starts at zero. ...
1
vote
0answers
19 views

probabilistically segmenting a rectangle

I am trying to find ways to segment a image randomly, but drawn from a probalistic distribution of pre-determined areas to be cut through. First thought was to pick random points and run Covex hull ...
0
votes
0answers
20 views

random walk on rotation matrix

I have a 3x3 matrix and I have to create a random process that rotate this matrix and such that there is a tipycal time of decorrelation of the matrix: the mean time needed to reoerient the matrix of ...
0
votes
0answers
104 views

Most likely position for random walk with symmetric jumps after $t$ steps

Consider a random walk on $\mathbb{Z}$ starting at 0 with jump distribution $p(x)$ such that, $p(x) = p(-x)$ $p(x)>0$ for all $x \in \mathbb{Z}$ Let $p^{\,t}(n)$ be the probability that the ...
0
votes
0answers
22 views

Maximum of random walk distribution for arbitrary jump distribution and even times

Consider a random walk with an arbitrary jump distribution on $\mathbb{Z}$ and zero expected increment. Let $p^t_n$ be the probability that at time $t$ the random walk is at $n \in \mathbb{Z}$. Is it ...
1
vote
1answer
40 views

Continuous-time Random Walk

Hi I have a question about the following definition. We want to define a random waldlk $S$ on $\mathbb{Z}^d$ in continuous time. For this let $p$ be the increment distribution of $S$. Then for each ...
1
vote
0answers
34 views

Probability of termination of random teleportation

In Minecraft, with mods, there's a liquid called Resonant Ender, which if you touch it, teleports you randomly up to 8 blocks on both the north-south and east-west axes. Consider an infinite sea of ...
2
votes
0answers
48 views

Excursion of random walk conditioning on return

Consider a simple random walk in one dimension starting from the origin. Let $\epsilon>0$. How to prove that, conditioning on the event that the random walk is at the origin at time $n$, the ...
2
votes
1answer
67 views

Comparing hitting probabilities vs comparing mean hitting times of a random walk on a graph

I am trying to understand random walks on graphs and whether an intuition that I have can be made rigorous mathematically, and whether it is also true. Let $G$ be a finite, connected undirected graph ...
1
vote
0answers
34 views

Prove that uniform distribution on a set of vertices $V$ is stationary if the graph is regular.

I was going through Random walks on graphs: A survey It was stated that: Uniform distribution on a set of vertices $V$ is stationary if the graph is regular. Can anyone give me some hints to ...
2
votes
1answer
32 views

Inequality for General random walks

Let $S_n=(S_n^1,...,S_n^d)$ be a random walk with distribution $p(y,z):=\mathbb{P}\{S_{n+1}=z\mid S_n =y\}=p(z-y)$. Then $\mathbb{P}\{S_{2n}=0\}\geq(\mathbb{P}\{S_2=0\})^n\geq p(x)^{2n}\forall x\in ...
0
votes
0answers
28 views

Infinite expected number of visits with Green function

The random walk Green function is defined by $G(x,1) = \sum_{n\in \mathbb{N}_0} P(S_n = x)$, with $x\in\mathbb{Z}^d$. $G(x,1)$ equals the expected number of visits to $x$. Now I want to prove that ...
1
vote
2answers
96 views

Showing stopping is finite almost surely

Consider a discrete random walk taking values +1 or -1 with probabilities p and q, respectively. Let $S_n = \sum_{k=1}^{n}X_k$. Let $[-A,B]$ be an interval, $A,B \geq 1$. Now define $$\tau =\min(n:n ...
1
vote
2answers
31 views

Clarification on Two-player Gambler's Ruin variant.

I looked around and found many questions related to two-player variants of Gambler's Ruin but could not find what I had in mind. I needed clarification on a certain step while deriving the expression. ...
0
votes
0answers
42 views

Hitting probabilities for random walk with +m/-n steps

Random walk theory in the real axis: a frog starts at k initially, and in each move, it moves either by distance m to the right (from i to i+m) or by n to the left(from i to i-n), where k,m,n are ...
2
votes
0answers
85 views

Expected distance of a random walk of distance $k$ on the $k$th step

I am trying to sharpen my intuition on some random-walk style results. Suppose we are looking at a random walk on $\mathbb{Z}$ starting at $0$. At the $k$th step, we either walk to the left $k$ ...
1
vote
0answers
47 views

2-dimensional random walk experiment

Question: Consider a board covered by square tiles(like a chess set only of a size of your choosing) and colored like a chess set. Two "people" are placed in different areas of the board and ...
3
votes
1answer
64 views

Step in computation of the expected cover time for the simple random walk on a discrete circle

I'm having a little trouble understanding part of an example in Lawler's Intro to Stochastic Processes ("Simple Random Walk on a Circle" example on page 32). The problem is the following: Suppose ...
0
votes
0answers
51 views

Can a Random Walk algorithm be considered a computational intelligence algorithm?

I am implementing different computational intelligence algorithms from the local search area. These are Hill Climbing and Simulated annealing. Also I am implementing another algorithm with a mere ...
0
votes
1answer
126 views

Probability Generating Function of a Stopping Time, Random Walk

Let $\{S_k\}_{k\geq0}$, $S_0=0$ be a symmetric simple random walk. For an integer $n\geq1$, let $\tau_n=min\{k\geq1:S_k\notin(-n,n)\}$ be the first time k such that $S_k$ leaves the region $(-n,n)$, ...
0
votes
0answers
41 views

Limit of Covariance and Correlation of Random Walk

Let $S_n=X_1+...+X_n$, $n\geq1$ be a random walk, where $EX_k=\mu$ and $Var(X_k)=\sigma^2$, $0<\sigma^2<\infty$. a)Find the covariance $Cov(S_n,S_m)$ and the correlation coefficient ...
7
votes
1answer
234 views

Last vertex visited by the symmetric random walk on a discrete circle

$n$ cats form a circle, indexed from $0$ to $n-1$. At first, there is a ball at the cat $0$. We throw a coin with the probability of $p$ heads up. If the coin is heads up, we pass the ball clockwise, ...
3
votes
0answers
29 views

Random walks with limited number of visits

I'm interested in random walks (esp. their hitting times) such that the number of visits to each state is limited by some parameter $K$. Is there any canonical name for such stochastic processes? ...
3
votes
0answers
78 views

Random walks intuition [closed]

I came across the reflection principle and this explanation at Is there an intuitive way to see this property of random walks? However, I can't understand the reasoning in the answer about mirroring ...
2
votes
1answer
17 views

Formula for the analytical computation of Eigenvalues for random walks of order one and two on regular lattices

I have a question with respect to random walk penalties in statistics. In Bayesian statistics an adequate prior for modeling a $n$-dimensional random vector $\boldsymbol{x}$ as a random walk of order ...
0
votes
1answer
26 views

Calculating the Variance of a Pure Random Walk

I am trying to calculate the first two moments of the random walk below: $y_t$=$y_0$+$\sum_{j=1} ^t u_j$ Mean: E[$y_t$]=$y_0$ Variance: E[$y_t ^2$]=t$\sigma^2$ I understand how to obtain the 1st ...
0
votes
0answers
38 views

When is a lazy random walk matrix positive definite?

There are a number of nice results about when the graph Laplacian is positive definite and positive semi definite. However, I can't seem to find any analagous results for random walk matrices, and was ...
0
votes
0answers
48 views

An exercise about random walk introducing to wiener process

I learn stochastic process by myself and currently, doing an exercise about random walk. Suppose a random walk $\eta(t,s)$, (1) $\eta(0,s) = 0$; (2) $\eta(t,s)$ is defined on a set of sample point ...
0
votes
0answers
26 views

How to model time changing random variables

Lets say I have a random variable $X(t)$ which describes some unit of motion of a living organism and $X(t)$ is itself a timeseries since this unit of motion changes in time. I would like to be able ...