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

learn more… | top users | synonyms

5
votes
1answer
1k 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" ...
10
votes
1answer
5k 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 ...
1
vote
1answer
345 views

Symmetric random walk with bounds

can anyone help me with this: We are considering a symmetric random walk that ends if level 3 is reached or level -1 is reached. Start=0 What is the expected number of walks? So I am looking for: ...
5
votes
1answer
542 views

Probability distribution for the position of a biased random walker on the positive integers

I initialize a biased one-dimensional random walk on the positive integers at the origin, $x = 0$, which also serves as a reflecting boundary blocking steps onto the negative integers. Let's say that ...
2
votes
3answers
3k 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. ...
1
vote
1answer
191 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 ...
4
votes
1answer
272 views

Conditional return time of simple random walk

Consider a simple symmetric random walk on $\mathbb{Z}$, $(S_t)_{t \geq 0}$. Call $\tau_k = \min\{t \in \mathbb{N}\, : \, \, S_t =k \}$, the hitting time of $k \in \mathbb{N}$. Call $\tau^* = \min\{t ...
12
votes
2answers
1k 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 ...
4
votes
1answer
489 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?
4
votes
3answers
520 views

Probability a random walk is back at the origin

I have a symmetric random walk that starts at the origin. With probability $1/6$ it goes right by one and with probability $1/6$ it goes left by one. With probability $4/6$ it stays put. After $n$ ...
3
votes
1answer
385 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 ...
2
votes
1answer
952 views

Expected number of steps till a random walk hits a or -b.

On wikipedia I read that the expected number of steps till a 1D simple random walk hits either $a$ or $-b$ is equal to $ab$. (I have seen this result also on other websites.) However, no proof or ...
0
votes
2answers
288 views

How to check that a sequence of numbers is random? [duplicate]

I have a sequence of numbers like 1,7,22,45,12,96,21,45,65,36,85,14,51,16,18,17,16....65... IS there any formula to check whether the sequence is random or not ? In my case odd numbers are ...
42
votes
1answer
2k views

Identity for simple 1D random walk

The question is to find a purely probabilistic proof of the following identity, valid for every integer $n\geqslant1$, where $(S_n)_{n\geqslant0}$ denotes a standard simple random walk: $$ ...
8
votes
6answers
342 views

simplify summation of factorial (random walk)

I suspect that the expression $$\sum_{n=0}^N \frac{(N-2n)^2}{n!(N-n)!}$$ simplifies to $$\frac{2^N}{(N-1)!}$$ But I cannot find the intermediate steps. Can someone give me a hint how I can deduce ...
1
vote
3answers
1k 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 ...
8
votes
1answer
154 views

How long until everyone has been in the lead?

Earlier, I asked a question about a series of competitions: A series of matches are held between n identical competitors. Each is won by one of the n with equal probability (no ties). I'm looking ...
5
votes
1answer
106 views

Recurrence for random walk

I have the following recurrence which I get when trying to solve a random walk problem given a positive integer $x$. $p_i = \dfrac{p_{i-1}}{2} + \dfrac{p_{i+2}}{2}$ if $0< i < x$ $p_i = 1$ if ...
4
votes
1answer
313 views

Random Walk on Z

Let $S_n$ be the symmetric random walk on $\mathbb{Z}$. How do i calculate $P(\limsup_{n\rightarrow\infty} S_n=\infty)$? I already know that the probability is 1 but I don't really know how to start? ...
2
votes
1answer
114 views

Showing that lim sup of sum of iid binary variables $X_i$ with $P[X_i = 1] = P[X_i = -1] = 1/2$ is a.s. infinite

Let $(X_i)_{i\in\mathbb{N}}$ be an i.i.d. sequence of binary random variables with $$P[X_i = 1]=P[X_i = -1] = \frac{1}{2}$$ and let $$S_n = \sum_{i=1}^{n} X_i.$$ I'd like to show that $$P[\lim ...
2
votes
3answers
125 views

Random walk problem in the plane

Let a particle in the plane $R^2$ executes random jumps at discrete times $t= 1, 2, ...$. At each step, the particle jumps from the point it is a distance of lenght one. The angle of any new jump ...
1
vote
2answers
1k 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 ...
11
votes
1answer
386 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 ...
8
votes
1answer
183 views

First player to win k matches

A series of matches are held between n identical competitors. Each is won by one of the n with equal probability (no ties). I'm looking for a probabilistic description of the outcome when looking at ...
5
votes
1answer
269 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 ...
4
votes
1answer
893 views

Random walk as a martingale?

Let $S_0$, $Z_1$, $Z_2$, $\ldots$ be independent random variables. $S_n=S_0+Z_1+\cdots+Z_n$, $n=0,1,2,\ldots$ $S_n$ is a random walk starting in a random point, $S_0$ I need to find out, when it is a ...
4
votes
1answer
187 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 ...
4
votes
1answer
325 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 ...
3
votes
1answer
661 views

Expected number of steps in a random walk with a boundary

Let's say I am trying to climb a flight of $N$ stairs. Each time I want to take a step, I flip a fair coin. Heads means I take a step up; tails means I take a step down. If I'm at the bottom of the ...
2
votes
1answer
72 views

Visits from a transient random walker on the integers

Consider a random walk $\{S_n\}$ on $\mathbb{Z}$ with forward probability $p>\frac12$. It is known for such a transient RW that each site is a.s. visited only finitely many times. However, is it ...
2
votes
3answers
281 views

Random walk returning probability

Consider a two-dimensional random walk, but this time the probabilities are not $1/4$, but some values $p_1, p_2, p_3, p_4$ with $\sum p_i=1$. For example, from $(0,0)$, it goes to $(1,0)$ with $p_1$, ...
2
votes
0answers
99 views

random walk with possibility to freeze

Consider a Random Walk on a one-dimensional lattice. The walker starts moving at time $0$ from $x=0$. At every step, the walker moves to the right with probability $p$, to the left with probability ...
2
votes
2answers
158 views

Mixing time for a random walk on an interval

I take a random walk on a bounded one-dimensional interval of length $N$, with possible walker positions $1$ through $N$. If I start at position $1$, how many steps should it take before my walker is ...
2
votes
0answers
126 views

Repeated reflection

This is a problem from Feller's book introduction to probability theory and its application, Vol 1, Chap 3 problem 3. Let $a$ and $b$ be positive, and $-b <c<a$. Prove the number of paths to ...
1
vote
2answers
59 views

Random walk confusion

If a ransom walk is binomial (1/2 probability of going forward, 1/2 backward) why isn;t the variance a) $\sigma=(\frac{n}{4})^.5$ b) instead of $\sigma=(n)^.5$ these sources seem to give ...
1
vote
0answers
170 views

Reference Request, Random Walk [duplicate]

The expected distance from origin after a random walk of $N$ steps in a $d$ dimensional space, is close to ...
0
votes
1answer
103 views

Average end point of 1-dimensional random walk?

Is it possible to estimate the average end point of a 1-dimensional random walk of n steps where the probability of going "left" is p and going "right" is 1-p? Thanks.
0
votes
1answer
639 views

Expected hitting time of one of two barriers

In the webpage "hitting time of one of two barriers", the probability that a non symmetric random walk hits one of two barriers is computed. The walker starts from $x=0$ and the barriers are located ...
0
votes
2answers
254 views

hitting time of one of two barriers

Let's consider a one-dimensional Random Walk. At each time the walker moves of one step to the right with probability $p$ and to the left with probability $q$, with $p+q=1$. The walk is not symmetric, ...
0
votes
1answer
817 views

Stationary distribution for directed graph

I want to implement the algorithm of graph partitioning of sparse directed graph. In this algorithm after computing the transition matrix ,we should compute the stationary distribution of the random ...
0
votes
2answers
303 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 ...