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

learn more… | top users | synonyms

0
votes
0answers
15 views

Bound on Poisson process

In a proof of a theorem I have the following situation: $N_t$ is a Poisson random variable with parameter $t$. From a corollary we get the following result: Let $X_1,X_2,\dots$ be independent, ...
1
vote
0answers
130 views

What is the probability a random walk crosses a line before another?

Let $n \geq 0$, $X_n$ be a random walk, where $X_{n+1} = X_n + 1$ with probability $p$, and $X_{n+1} = X_n - 1$ with probability $1-p$. $X_0 = 0$ Let $l_n, r_n$ be a sequence of integers, where for ...
1
vote
1answer
46 views

Applications of Random Walks for undergraduate students

Students are asking for applications of discrete random walks in "real life" problems. By real life they mean financial applications and industry. We have two more weeks on this subjects and I'm ...
1
vote
0answers
46 views

Triangular inequality for n-th step distributions

Assume that $p_n$ is the $n$-th step distribution of a random walk with state space $\mathbb{Z}^d$, i.e. $p_n(x,y)=\mathbb{P}(S_{n+1}=y\mid S_0=x)$, where $S_n=S_0+\sum_{i=1}^nX_i$ with $X_i$'s i.i.d. ...
2
votes
0answers
125 views

Gambler's Ruin with no set target for win

I have been presented with the following probability question: A compulsive gambler is never satisfied. At each stage he wins $€1$ with probability $p$ and loses $€1$ otherwise. Find the probability ...
0
votes
1answer
38 views

Number of random walk paths crossing horizontal line

I have series of binomial variables $\xi_1, \xi_2, \dots, \xi_n$ which form a random walk. Variables can be $\pm 1$ with probability $\frac{1}{2}$ and we define $S_n = \sum_{i=1}^n \xi_i$. We start ...
1
vote
0answers
29 views

Eigenvector/value of a biased random walk with a sink and a wall

Suppose you have a one dimensional random walk, with a wall at $S=0$ and a sink at $S=n$. The walk is biased so the odds of moving down vs moving up are $b:1$. More concretely, the transition graph ...
0
votes
0answers
26 views

Expected steps for ant on a cube, [duplicate]

There is an ant on a vertex of the cube, he's trying to get to the opposite vertex, what's the expected steps for it to take before reaching the opposite vertex? Ant can move in any directions along ...
1
vote
0answers
53 views

Expected number of steps for a random walk- robot

A robot is located at the top-left corner of a m x n grid The robot is trying to reach the bottom-right corner of the grid, he can move randomly in any of the directions: up, down, left, right. ...
1
vote
1answer
73 views

Properties of a random walk [closed]

First of all, I know nothing about Markov chains, and I'd like to prove the following without using the theory around them. Let $(M_{n})_{n\geq 1}$ be a random walk over $\mathbb{Z}$, starting at ...
0
votes
0answers
28 views

Mean absolute distance for a symmetric random walk

I have found that the mean absolute distance for a symmetric random walk after n steps can be computed using this product: What can be deduced from this? For example how can variance be computed ...
3
votes
0answers
20 views

The boundedness of a certain sequence of expectations

In Bálint Tóth's paper, "No More Than Three Favourite Sites for Simple Random Walk", while proving one of the many technical lemmas in his theorem's proof, he makes the following claim: suppose for ...
0
votes
1answer
59 views

Help with a random walk problem.

Let $\xi_1,\xi_2,...$ be a sequence of random variables such that $\xi_i=-1$ or $\xi_i=1$ for $i=1,2,...$. Let $x(n)$ be the position of a random walk at time $n$, i.e. $x(n)=\xi_1+\xi_2+...+\xi_n$. ...
2
votes
1answer
49 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
52 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
33 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
81 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
79 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
51 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
31 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
34 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
33 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
140 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
39 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
68 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
57 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
71 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
61 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
33 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
21 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
105 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
42 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
50 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
37 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
33 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
98 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
89 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$ ...