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

learn more… | top users | synonyms

3
votes
2answers
607 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
170 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
265 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, ...
11
votes
1answer
346 views

Does this modified random walk (2D) return with probability 1?

Pólya showed that a random walk (with the directions at each step uniformly distributed) on the integer lattice returns with probability 1. What if instead we consider the random walk where we are ...
2
votes
2answers
262 views

What does it mean for MCMC to converge?

I know that a Markov Chain is a discrete random process where the current state decides the next and in a random walk, the probability that we move from node u to v is 1/N(u). An MCMC sample will ...
2
votes
2answers
261 views

Are probabilities proportional to the distance traveled in a random walk? What if the initial position is a bit biased?

A marker is placed at zero on the number line and a fair coin is flipped. On each flip we move one unit to the right. If it lands on heads, the marker is moved one unit up. If it lands on tails, the ...
0
votes
1answer
330 views

Probability mass function of a random walk process

Let $Y_n$ be a random walk process defined as $Y_n = Y_{n-1} + X_n$; $n = 1,2\ldots$ and $Y_0 = 0$, where $X_k = +1$ with probability $p$ and $-1$ with probability $1-p$. Write down the pmf for $Y_n$, ...
2
votes
1answer
115 views

1D random walk with infinite crossings

Let $x_i$ be a uniformly random real in $(-1,1)$. And let $f(x)$ be a strictly increasing positive and unbounded function. Let $S_j(f)=x_0/f(0)+x_1/f(1)+x_2/f(2)+\cdots+x_j/f(j)$ Does $S_j(f)$ ...
0
votes
2answers
168 views

Question from section 1.5 of Chung's Spectral Graph Theory

I'm (slowly) reading Fan Chung's Spectral Graph Theory. At the moment, I'm in section 1.5 which is about eigenvalues and random walks. There's a small technical point that puzzles me. The context ...
1
vote
1answer
173 views

Returning Paths on Cubic Graphs

Suppose we have a 3-edge-colorable cubic graph with $N$ vertices. How many paths of length $N$ exist that return to its origin? Or putting it differently: What is "Pólya's Random Walk Constant" on ...
1
vote
1answer
70 views

Degree of girraphs

A girraph is an infinite, regular, vertex-transitive graph, on which a random walk is recurrent. The random walk on the square grid returns to the origin with probability 1, and for the cubic grid ...
2
votes
1answer
95 views

Restricted random walk in $\mathbb Z^3$

What is the proability to return to the origin, for a uniform random walk on the integer lattice in $\mathbb Z^3$, if we are restricted to $x \geq 0$? I.e. if we try to step into a negative ...
1
vote
1answer
62 views

What is the lowest dimension $d$ for which the simple random walk on $\mathbb Z^d$ is transient?

By "transient" I think they mean that the probability of returning to the initial point is $<1$.
1
vote
2answers
613 views

Expectation of Random Walk

At each time step, I have 1/2 probability of walking one step to the right, and the same probability of walking one step to the left. Let X be the random variable corresponding to the final ...
3
votes
2answers
672 views

Definition: transient random walk

What exactly does a "transient random walk on a graph/binary tree" mean? Does it mean that we never return to the origin (assuming there is one as for the tree) or just any vertex of the graph or ...
2
votes
1answer
129 views

Expectation of $T^2$ where $T$ is the absorption time at ${a,−a}$ of a simple random walk $\{S_n\}$

I asked a very similar question before: Expectation of $TS_T$ where $T$ is the absorption time at $\{a,-a\}$ of a simple symmetric random walk $\{S_n\}$ But this time I have an ASYMMETRIC random ...
1
vote
2answers
747 views

What are some martingales for asymmetric random walks?

Here are some examples for symmetric ones: http://mathoverflow.net/questions/55092/martingales-in-both-discrete-and-continuous-setting/55101#55101 Is there a similar list for asymmmetric random ...
4
votes
1answer
374 views

Expectation of $TS_T$ where $T$ is the absorption time at $\{a,-a\}$ of a simple symmetric random walk $\{S_n\}$

I was trying to calculate the expectation of $T^2$ using some martingale and got that I needed the expectation of $TS_T$. Any idea?
3
votes
1answer
306 views

Expectation of absorption time for a random walk which remains at n with probability 1/2

A random walk moves from k to k+1 with probability 1/2 and to k-1 with probability 1/2, except when k=n, in which case it remains at n with probability 1/2 and moves to n-1 with probability 1/2. ...
3
votes
1answer
211 views

Solving a maze by taking a random walk

I vaguely recall a result like the following from one of my complexity theory classes in school: given a 2d maze (which I guess we can think of as a directed graph with a fixed start node and exit ...
5
votes
1answer
232 views

Asymptotic behavior for the return to zero of a simple random walk

I got stuck today trying to understand an argument of the Frank den Hollander Book's. The problem is described below. Let $S_n=\sum_{i=1}^n X_i$ be the simple random walk in $\mathbb{Z}^d$, that is ...
0
votes
1answer
39 views

Cardinals arising from random walks in the limit

A random walk $X$ is a sequence of elements of the set $\{-1, 0, 1\}$ and $X_i$ denotes the $i^{th}$ element of $X$. Consider the set $C_n$ of all random walks of length $n$ and the set $C_\infty = ...
1
vote
0answers
511 views

Help needed solving for bounded random walk expectation; problem involves strange (to me) Factorial/Gamma-function summation

Posted this at math overflow, but they redirected me here. I'm currently trying to solve for the expectation of a bounded Gaussian random walk. That is to say, each step is a random variable with ...
8
votes
3answers
805 views

Biased Random Walk and PDF of Time of First Return

I have a random walk process where each step the probability of $+1$ is $p$ and $-1$ is $q$, with $p+q=1$. $p$ may not equal $q$. The walker starts at zero. I want to know the probability that the ...
7
votes
1answer
495 views

Question about random walk with fixed endpoint, and a reference request

We have a random walk of length $n$, starting at $0$ and ending at $-6\,\sqrt{n}$. Can we give any sort of high probability bound on the number of steps before we first reach the value $-2\, ...
2
votes
1answer
230 views

considering the minimum in random walk

Grimmett and Stirzaker's "Probability and Random Processes" gives a nice discussion about random walk, for example, it considers $M_n=\max\{S_i,0\le i \le n\}$ where as usual ...
2
votes
1answer
96 views

$1$D bidirectional random walk question

In a $1$D random walk on x axis a particle can turn left with probability $\frac{3}{4}$ and right with probability $\frac{1}{4}$. What is the probability that $|x|\leq 1 $ for $1\leq ...
5
votes
1answer
2k views

Probability of a biased random walk hitting an absorbing barrier in some number of steps

Let's say I have a biased random walk over the integers in some interval [0, L] where the endpoints of the interval ('0' and 'L', respectively) are fully absorbing. The walker starts at some position ...
2
votes
1answer
441 views

Hitting time for a random walk where step probabilities linearly depend on the distance to an absorbing wall

Consider the case where I have a discrete random walk on the integers over an interval $[0, M]$, where I start at some position $0 < k < M$, and both endpoints (i.e. $0$ and $M$) are fully ...
1
vote
1answer
188 views

analogy to ruin problem against infinitely rich adversary

I realized that an earlier question I'd posted was actually different than what I was actually asking. My question is: say we have a game where you win 2 dollars, or lose 1 dollar, both with ...
3
votes
1answer
215 views

Random Walk - If $m$ is odd, probability of no equalization in the last $m$ steps in path of length $2m$ is 1/2

I am trying to solve the problems in the Chapter 12 Random Walks of Introduction to Probability by Grinstead and Snell. I am stuck at Problem 6(b) which I quote below (page 482) Problem 6 (a) Show ...
3
votes
1answer
361 views

Random walk $< 0$

Suppose ${X_t}$ is a random walk with mean zero. (either discrete or continuous time) Fix a time $T$. What is: $P[X_t < 0 \text{ for all } t \leq T]$? In words, what's the probability the random ...
3
votes
1answer
320 views

Analysis of a biased random walk related to median finding

Imagine a process with two variables min and max, and two counters hi and lo. We initialize min and max by selecting two random numbers (assume a uniform (0,1) distribution for convenience), and ...