For questions on random walks, a mathematical formalization of a path that consists of a succession of random steps.
6
votes
2answers
259 views
A question on calculating probabilities for the random walk
I am currently working on a high school project revolving around the 'Cliff Hanger Problem' taken from ”Fifty Challenging Problems in Probability with Solutions” by Frederick Mosteller.
The problem ...
2
votes
1answer
112 views
random walk on finite graph
I know that the stationary distribution of a random walk on the graph is given by,
(degree of the node)/(2*total number of links in graph). My question is, how do we get this solution?
2
votes
2answers
237 views
Drunk person walking in 1D desert
Given $f(x)$, a strictly positive monotonically decreasing sequence, converging to 0.
How to check whether a one dimensional random walk with stepsize $f(n)$ in random direction at the $n$-th step, ...
2
votes
2answers
257 views
one-dimensional random walk
Consider a one-dimensional random walk whose steps are $+2$ and $-1$ with probabilities $p$ and $1-p$ respectively, starting from $0$ and in the interval {$-n$, $n$}. The walk ends at $-n$ or $n$ or ...
3
votes
2answers
214 views
Random walk and its expectation
Let $S_n=X_1+X_2+...+X_n$, where $X_i=1$ with probability $p$ and $X_i=-1$ with probability $q=1-p$, for all $i$ and independently of each other. Assume that $S_0=0$ and $0<p<\frac{1}{2}$.
...
2
votes
3answers
87 views
Derivation of Wiener process first passage times using probability generating function?
I would like to find the distribution of first passage times in a simple Wiener process using the idea of probability generating functions. Thus there will be, at certain point, a limiting step to go ...
4
votes
1answer
141 views
The probability of a “double supremum” of random variable
Let $X_1,X_2,X_3,\ldots$ be IID r.v. with
\begin{equation}
P(X_i<-1)=0
\end{equation}
\begin{equation}
P(X_i<0)>0
\end{equation}
\begin{equation}
P(X_i>0)>0.
\end{equation}
Define
...
2
votes
0answers
87 views
Probability distribution of a self avoiding walk
Preliminary:
Consider a walk on the lattice $\mathbb{Z}_d$ lattice of length $N$. In a normal random walk, if we let $N$ get large the end position has a probability distribution (PDF) that looks ...
1
vote
1answer
122 views
Wiener process question
When I look up the definition of 'Wiener process' at Wikipedia, it tells me:
$W(0) = 0$ and $W(t) - W(s) \sim N(0, t-s)$.
When I try to simulate this in matlab, I get different results when I define ...
3
votes
1answer
100 views
what is the behaviour of moving dot with 50% chance to go left or right?
If a dot is moving (from zero) left or right, by one, with 50% chance to go left or right - is it going to go to the +inf or -inf when it has infinite moves?
3
votes
1answer
111 views
A difference equation related to RW on Hypercube
I am trying to solve the following recurrent relation
$$
T(n)=\frac{n}{m}T(n-1)+\frac{m-n}{m}T(n+1)+1, \,\, \text{subject to } T(m)=0
$$
Where $0\leq n\leq m$ and $m$ is a fixed integer. I have ...
0
votes
1answer
198 views
Stopping time and random walk: Proof that Stopping time of reaching a certain value is finite a.s. [duplicate]
Possible Duplicate:
Proving that 1- and 2-d simple symmetric random walks return to the origin with probability 1
This is a basic question but I was wondering if there was a simple proof (I ...
0
votes
1answer
80 views
A random walk on $\mathbb{Z}$ with a twist
I am trying to decide whether the following random walk is recurrent or not. Intuitively, I think it is - but I am not familiar with techniques of proving it.
My random walk is the following: on each ...
1
vote
1answer
132 views
Variation of a simple random walk
Consider the following problem.
A particle takes discrete steps $\sigma_1, \sigma_2, \sigma_3, \ldots, \sigma_n$ which take on values $+1$ or $-1$. However, $P(\sigma_i = +1) = p$ if $i$ is odd and ...
4
votes
1answer
152 views
Circular random walk
Suppose we have a circumference divided in N arcs of the same length. A particle can move on the circumference jumping from an arc to the adjacent, with probability $P_{k \to k-1}=P_{k\to ...
1
vote
1answer
135 views
A problem about the expectation of maximum rise up for a random walk.
Give such a random walk moving on the x-axis:
Start from $x_0=0$;
After the $i^{th}$ step, the location is $x_i$.
The length for the $i^{th}$ step $x_i-x_{i-1}$ is a uniformly generated real number ...
0
votes
0answers
104 views
Expectation of the maximum consecutive subsequence sum of a random sequence
There is a problem from Programming Pearls 2nd edition (Problem 4 in Chapter 8.7):
If the input elements in the input array are random real numbers chosen uniformly from [-1,1], what is the ...
5
votes
0answers
136 views
Where does directed random walk hit the boundary?
I have a problem that I more or less know the answer to, but would really like to see it done in a systematic, rather than ad hoc way. In spite of this, I will pose the question in a very concrete ...
1
vote
1answer
114 views
Biased alternating random walk on a lattice in 1D
Let's consider a random walk on a fixed lattice with step size 1 in 1 dimensions. In variation to the broadly discussed basic case, with a probability p the next step will be in the opposite direction ...
2
votes
1answer
105 views
A problem about symmetric random walk
Consider a symmetric random walk $P(X_i=1)=P(X_i=-1)=1/2$, $S_0=0$, $T_a=\min(n:S_n=a)$
We already know that $P(T_a>T_{-b})=1-P(T_{-b}<
T_a)=\frac{b}{a+b}$ and $E(\min\{T_a,T_{-b}\})=ab$.
...
2
votes
0answers
52 views
Completeness of random walks in multiple dimensions?
I was reading Artificial Intelligence: Modern Approach (Norvig and Russell), and there was a footnote that really caught my attention. I apologize if the problem is more in the domain of CS than ...
1
vote
3answers
767 views
biased random walk on line
Lets say we start at point 1. Each successive point you have a, say, 2/3 chance of increasing your position by 1 and a 1/3 chance of decreasing your position by 1. The walk ends when you reach 0.
...
0
votes
1answer
127 views
Random walk on infinite line - can it be stationary?
Suppose a random walk on an infinite line $[...-3,-2,-1,0,1,2,3,...]$, starting from 0. Probability to go right or left are equal.
Does such a process stationary?
I think that it is NOT, since the ...
2
votes
1answer
214 views
Non-symmetric simple random walk stopping time
Say there is a random walk $\{S_n\}$ with $S_0=0$ and $0<p=P(S_1=1)<\frac{1}{2}$. We know such a random walk would go to $-\infty$ eventually. Define the stopping time $T=\inf\{n: S_n=-\infty\}$, ...
1
vote
2answers
133 views
Is this random walk well studied?
Suppose that we have an ergodic finite Markov chain $C$ with a fintie state space $S$, and
we have random variables $X_s$ where $s\in S$. Consider
the following random walk
$S_0=0$ and $S_{i+1}=S_i ...
2
votes
1answer
59 views
Is there an unbiased random walk on a colored plane for any number of colors?
So I was trying to motivate the fundamental postulate of statistical mechanics (i.e. all microstates are assumed to be equally probable $-$ even if we can't practically measure them, but only their ...
1
vote
2answers
69 views
Random Walker Problem - Help Needed
I need some help solving this problem.
A man is about to perform a random walk. He is standing a distance of 100 units from a wall. In his pocket, he has 10 playing cards: 5 red and 5 black.
He ...
1
vote
1answer
45 views
question on graphs and expected steps
So we have an undirected graph with vertices labeled 0,1...n. We start at 1 and we can go either left or right . We want to know the # of steps expected to get to 0.
I figured that half the time you ...
1
vote
1answer
54 views
random walks question
The probability that a simple random walker is at 0 after $2n$ steps is $P(S_{2n}=0)=\binom{2n}{n}2^{-2n}$. What is the probability that a random walker is at integer $2j$?
Well, I understand ...
1
vote
1answer
86 views
The probability of a discrete-time random process ever incurring a certain drop from “peak to bottom”
Background. Let $Y_1,Y_2,\ldots$ be i.i.d. random variables such that
$$P(Y_i<-1) = 0,$$
$$P(Y_i<0) > 0,\quad P(Y_i>0)>0,$$
$$E[Y_i] = \mu > 0\qquad \text{($\mu$ is finite)}.$$
Now ...
1
vote
0answers
111 views
Random walk in a sphere
Given a sphere of radius $R$, divided in cubic cells of size $l$, the probability for a particle to jump from a cube to another adiacent is: $P=\frac{1}{6}$. If we define the probability to exit from ...
2
votes
1answer
353 views
Mean distance from origin after $N$ equal steps of Random-Walk in a $d$-dimensional space.
I am looking for a formula that evaluates the mean distance from origin after $N$ equal steps of Random-Walk in a $d$-dimensional space.
Such a formula was given by "Henry" to a question by "Diego" ...
1
vote
2answers
163 views
Random walk with reset?
Is there such a random walk, that "good times" it just looks like a random walk, while when "bad moment" comes, it will reset => jump to zero, afterwards continue doing random walk again? Thanks!
1
vote
3answers
486 views
Random walk problem
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 ...
0
votes
1answer
88 views
Random walk and powers of 2
I'm in trouble on the following problem:
given a random walk starting at point N on the integer number line, how many steps should I wait before the walk hits a power of two at least once, with ...
8
votes
2answers
382 views
Random walk on n-cycle
For a graph G, let W be the (random) vertex occupied at the
first time the random walk has visited every vertex. That is, W is the last new
vertex to be visited by the random walk. Prove the following ...
3
votes
1answer
144 views
understanding a proof of the hitting time theorem for a right-continuous random walk using generating functions
This is particularly directed at those who have Grimmett & Stirzaker, Probability and random processes (2005), at hand.
It pertains to the proof step prior to equation (10), p. 166.
For others:
...
1
vote
1answer
261 views
Random (drunkard) walk distance after $n$ steps
I am tying to analyze a random walk on an integer lattice $\mathbb{Z}^k$. For $k=1$, what is the probability that after $n$ steps the drunkard's distance from the origin is lower than $\sqrt{n}$?
1
vote
0answers
163 views
Random walk with increasing step size
A random walk in the plane with step size $f(n)$ is cool if there is some constant $C$ such that it returns within a distance $C$ of the origin infinitely many times with probability $1$.
At the ...
1
vote
0answers
99 views
Ergodic process and random walk
Is a gaussian random walk process an ergodic process? If Yes, does someone knows the proof?
Thanks in advance
3
votes
2answers
224 views
Expected value of function of random walk
I am trying to calculate $\lim_{n \to \infty} {E[e^{i \theta \frac{S_n}{n}}]}$. Where $\theta \in \mathbb{R}$, and $S_n$ is simple random walk.
I could simplify it to $\lim_{n \to \infty}E[\cos(\theta ...
0
votes
2answers
179 views
Gambler's Ruin with varying probabilities
Consider a random walk $X_j$ on $\mathbf{Z}$ that starts at $X_0 = k \in \{1, 2, \dots, N-1\}$. Let $T$ be the random time defined by $T = \min \{j | X_j \in \{0,N\}\}$ . Then if ...
1
vote
0answers
122 views
Non-uniform random walk
I'm searching a solution for this problem:
Given a segment of length $L$, from $0$ to $L$ divided in $N$ subsegments of the same length, a particle, starting from the subsegment in $x_k$ has a ...
4
votes
1answer
2k views
Expected Value of Random Walk
Can someone very simply explain to me how to compute the expected distance from the origin for a random walk in $1D, 2D$, and $3D$? I've seen several sources online stating that the expected distance ...
2
votes
1answer
231 views
Biased random walks in 2d
I'm looking at a random walk on a square lattice with a bias toward the origin. Any step away from the origin occurs with probability a probability p, which is less than the unbiased value of 1/4. I'd ...
0
votes
0answers
90 views
Nonexistence of invariant probability with respect to random walk
We have a random walk process $X_{k+1} = X_{k} + Y_{k}$, where $Y_k$ are independent random values with the same distribution, $X_{0}$ have some fixed distribution $\pi$. Let $P^{k,s}(x,B)$ be a ...
3
votes
0answers
46 views
Diffusion on a graph and its dual
Is there a relation between the diffusion of a random walker on a planar graph and that on the dual of the graph? It seems perhaps intuitive that if the diffusion on the graph is slow (in comparison ...
3
votes
2answers
474 views
Random walk probability/expected value
With what probability, starting at node $g$, does node $d$ get hit before node $e$ in the graph below?
What is the expected value of number of steps you need to hit $\{d,e\}$ (at least one of them) ...
4
votes
1answer
133 views
Biased lower bounded random walk
I have a random walk with the following rules:
It starts at 2
At each step it goes up by 1 with chance .4, down by one with chance .4 and up by 2 with chance .2
The walk ends if it reaches 0
I ...
6
votes
0answers
234 views
Is there a connection between the 3D random walk constant and the partition function?
In thinking about this question, I took a look at Pólya's random walk constants and was struck by the fact that an expression for the constant for a three-dimensional random walk,
...
