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
17 views

Find the probability generating function $G(s)$ of this branching process.

Suppose that $X_n$ is size of the $n$th generation of a branching process started from a single individual, where each individual has a random number of children with probability mass function: ...
0
votes
1answer
27 views

Escape probabilities in a random walk.

So, a lot of theory in symmetric random walks seems to concentrate on 'hitting/stopping times' and things like that. So I started wondering... How would I go about calculating the probability of ...
2
votes
1answer
52 views

Can someone help explain a proof from Feller Vol1 III.5?

One will need a copy of Feller's text (3rd edition) to answer this question. The proof I'm having difficulty with is Theorem 1, pages 84-85. When he discusses the r=1 case, he says ... "To the ...
-1
votes
2answers
33 views

Events With States - Random Walks [on hold]

A mosquito is walking at random on the non-negative number line. She starts at $1$. When she is at $0$, she always takes a step $1$ unit to the right, but, from any positive position on the line, she ...
2
votes
0answers
15 views

Consequence of random walk with positive speed on a graph

Consider a random walk $X(n)$ on a vertex-transitive graph where the random walk has positive speed, i.e., $$ \lim\limits_{n \rightarrow \infty} \frac{d(X(n), X(0))}{n}= \alpha>0$$ almost surely. ...
5
votes
1answer
50 views

A number-theoretic random walk on the integers

Suppose a random walker starts at $S_0 = 2$, and walks according to the following transition probabilities: If the walker is on the $n$th prime number $p_n$, she moves to either $p_n + 1$ or ...
2
votes
0answers
21 views

Why do we use an exponential Martingale for the stopping time of a BIASED random walk?

The following is a passage from the lecture notes: Let a simple random move to the right with probability $p$ and to the left with probability $q = 1 − p$. We want the probability that it hits ...
0
votes
1answer
48 views

Limit of random walk on $\mathbb{Z}$

$$\limsup_{n \to \infty} \frac{S_n}{\sqrt{n}}=+\infty, \quad\liminf_{n \to \infty} \frac{S_n}{\sqrt{n}}=-\infty \quad P\text{-a.s.}$$ Here $S_n$ is a random walk on $\mathbb{Z}$. I managed to show ...
4
votes
0answers
19 views

The maximum number of random walks of length N amongst all rectangles in Z^2 is maximized for a square.

I'll first define a rectangular graph $(m,n)$ to be the subset of $Z^2$ with vertices given by $(i, j)$ where $1 \leq i \leq m, 1 \leq j \leq n$. The graph has an edge between two vertices if they ...
1
vote
1answer
74 views
+50

Probability of absorption of a biased random walk when the starting point has binomial distribution

Consider a random walk $\{0,1, ... , N\}$ with up probability $p$ and down probability of $p-1$ where $p \neq 1/2$. Suppose there are absorbing barriers at $0$ and $N$ and that the starting point, ...
1
vote
0answers
22 views

Easy Question from Application: Estimate for transition probabilities of random walk - finding a coupling

SHORT VERSION: Find appropriate Coupling Suppose we have a random walk on the natural numbers, where we go to the left with probability $p_L \geq \frac{1}{6}$, to the right with probability $p_R\leq ...
3
votes
1answer
43 views

Class of graphs with symmetric random walk

Let $(V,E)$ be a graph and let $X_n$ be a random walk on the graph. At every step, the walker at $x$ jumps to one of the neighbors drawn uniformly at random among all the vertices $y$ such that there ...
1
vote
0answers
24 views

One dimensional Lazy random walk, $O(1/\sqrt{n})$?

Suppose that we have a Lazy 1-dimensional random walk $X_n$ valued in $\mathbb{Z}$, i.e. $$X_n = \sum_{i}^{n} \xi_i\;\;\;\;\;\;\;\;(\xi_i\;\text{iid}) $$ and $$\frac{1}{4}=P(\xi_1= 1)=P(\xi_1 =-1) ...
1
vote
0answers
27 views

A 'mix' of simple and lazy simple random walk

Consider a $\mathbb{Z}$ valued markov chain $X_n$ which evolves as follows. $$P(X_{n+1}=y | X_n) =\begin{cases} \frac{1}{2}, y=X_n+1, X_n-1, |X_n|>K \\ \frac{1}{4}, y = X_n-1 , y= X_n+1, ...
3
votes
3answers
48 views

How to show $M_n = X_n^2-n$ is a martingale?

Let $X_n, n = 0, 1, 2, . . .$ denote an unbiased Normal Random Walk. $X_0 = 10$, and $X_{n+1} = X_n + Y_{n+1}$, with $\{Y_n\}$ are i.i.d. $N(0, 1)$. Then how can I show that: A) $M_n = X_n^2-n$ is a ...
-1
votes
0answers
43 views

Clarify a question's answer related to random walk. [closed]

I'm studying Problem5.3 and its solution. However, its solution is not clear for me. Please explanatorily show this answer . I need to learn such type of questions. Please help me. Thank you.
4
votes
1answer
60 views

A random walk question: what is the given probability?

Let $\{X_n\}_{n\in\Bbb N_0}$ be a simple random walk, given $n\in \Bbb N$ what is the probability $$ \mathbb P(X_1\ge0,X_2\ge0,\ldots, X_{2n-1}\ge0,X_{2n}=0) $$ I think that I should benefit from ...
1
vote
1answer
19 views

Differentiating Spitzer's identity

Let $(S_n)$ be an arbitrary random walk. Define $$M_n:= \max(0,S_1,...,S_n)$$ and $$S_n^{+} := \max\{0,S_n\}.$$ Spitzer's identity states that for $0<r<1$, we have $$\sum_{n=0}^{\infty} r^n ...
-1
votes
1answer
34 views

Consider the gambler's ruin with equal probability of winning and losing each game. Find expected number of games until the gambler leaves.

Consider the gambler's ruin with equal probability of winning and losing each game. Find expected number of games until the gambler leaves (either because she has 0 dollars or reaches the house limit ...
1
vote
3answers
45 views

$N^{1/2}$ and randomness

I apologize if this question is overly vague, but part of the reason I am asking is because I don't know a more precise way of discussing these ideas. To state a general question: What, if any, ...
6
votes
1answer
42 views

If I wanted to randomly find someone in an amusement park, would I be faster roaming around or standing still?

Assumptions: The other person is constantly and randomly roaming Foot traffic concentration is the same at all points of the park Field of vision is always the same and unobstructed Same walking ...
0
votes
1answer
33 views

Distribution of particles at infinite time

Let any site of $\mathbb{Z}$ host a number of particles $\eta_0(x)$ which is distributed according to some probability distribution independently and identically for any site $x \in \mathbb{Z}$. At ...
11
votes
3answers
294 views

Random walk on natural number

Problem: You are standing at the position $0$ on the line of natural numbers $0, 1, 2, ..., n$. From this position you go to $1$ with probability $1$, but from any other position $i$ you go to $i+1$ ...
3
votes
1answer
33 views

On random rotational fluctuations in $\mathbb{R}^n$

Imagine first a disk that is mostly stationary, except for random ("thermal" if you like) "rotational fluctuations" around its axis (which is fixed). Something a bit like what's shown in the figure ...
1
vote
0answers
65 views

distribution of the length for a random walk on an infinite 2D grid

In connection with the flatland paradox, consider a 2D-random walk $(X_n)$ on $\mathbb{Z}^2$: the four moves of length one to W,E,N, and S are equaly likely at each time. For a fixed number of moves ...
1
vote
1answer
16 views

Integrate bivariate normal distribution over circular region

Context: Need to compute the probability that a 2D Gaussian random walk falls within distance $ d $ of some point $ p $ on the next step. (Assume the covariance $ \Sigma $ is the identity matrix $ I ...
1
vote
2answers
32 views

Random walk on vertices of a cube

If a particle performs a random walk on the vertices of a cube, what is the mean number of steps before it returns to the starting vertex S? What is the mean number of visits to the opposite vertex T ...
1
vote
1answer
27 views

Show a random walk is transient

I was going through some problems related to Markov chains and I got stuck on this bit: We are given a random walk on $Z$, defined by the transition matrix $p_{i,i+1}=p$ and $p_{i,i-1}=1-p$. How to ...
2
votes
0answers
17 views

Biased Asymmetric Random Walk [duplicate]

Consider the random walk $S_n$ given by: $$ S_{n+1}= \left\{ \begin{array}{ll} S_n + 2 & \mbox{w.p } p\\ S_n -1 & \mbox{w.p } 1-p \end{array} \right. $$ Assume that $S_0=n > 0$ ...
0
votes
1answer
33 views

Find E(min(Ta, T-b)) in Simple Random Walk

Let $T_x$ denote the first time a symmetric random walk visits $x$. (The random walk starts at $0$.) Find $\mathsf E(\min(T_a, T_{-b}))$ where $a, b > 0$. Hint: we computed $P(T_a < T_{-b})$ ...
2
votes
0answers
30 views

If two Brownian motion starts and end at the same points, can we say something about there difference?

Let $X$ and $Y$ be two standard Brownian motions with mean $0$ and variance $1$, both started at zero. If we know that \begin{align} X_n &= Y_n, \end{align} for some $n>0$, can we say ...
1
vote
0answers
24 views

Is a linear random walk with jump recurrent?

Let $\lambda_0=10^5$ or any other large integer. Define the recursive "process": $\lambda_t=\text{sample from a Poisson distribution with mean }\lambda_{t-1}$. Is this process recurrent? I mean, after ...
0
votes
1answer
47 views

Approximating a joint pdf using normal density of two independent variables

I know that given these two random variables (which correspond to the $x$ and $y$ coordinates of a random walk after $n$ steps, their joint probability density function can be $approximated$ by a ...
0
votes
1answer
72 views

probability, random walk, Markov chain question

Let $P$ be a transition matrix for a regular Markov chain and let $w$ be it’s equilibrium vector. Show that $w$ has no zero entries.
1
vote
0answers
39 views

Multiple Anihilating Random Walks in a Ring (cycle)

I've been trying to solve this problem for a long time. Problem Let $R$ be a cycle with $2n$ nodes and assume there are $2k$ particles performing a simple random walk in this ring (i.e., they have ...
1
vote
0answers
17 views

Self-Avoiding Walk incorporating diagonals

How many paths are there between $(0,0)$ and $(n,n)$ if you include all eight common cardinal directions: North, East, South, West, Northeast, Northwest, Southeast, and Southwest. The only condition ...
25
votes
2answers
358 views

Random Walk Without Repetitions

Suppose that we simulated a random walk on $\mathbb Z$ starting at $0$. At each step, we transition from position $x$ to position $x-3,\,x-2,\,x-1,\,x+1,\,x+2,$ or $x+3$ with equal probability. If ...
2
votes
1answer
132 views

Probability of asymmetric random walk returning to the origin

Consider the random walk $S_n$ given by $ S_{n+1} = \left\{ \begin{array}{lr} S_n+2 & with & probability & p\\ S_n - 1 & with & probability & 1-p \end{array} ...
0
votes
0answers
30 views

Filtered Probability Space Understanding

Usually in my probability theory class, we define a filtered probability space in the background $\left(\Omega, F, \left\lbrace F_t \right\rbrace P\right)$ and do all of our work on that space. I'm ...
0
votes
1answer
31 views

Exit time of simple random walk on $[-a,b]$

It can be proved using martingales and the optional stopping theorem that the expected exit time of a random walk on $(-a,b)$ beginning at $0$ with $a,b>0$ is $ab$. How can this be shown using a ...
0
votes
0answers
36 views

If there are two different stationary distributions, then there are infinitely many distributions in reducible markov chain

If there are two stationary distributions μ1 and μ2 there are actually infinitely many stationary distributions: (pμ1 + (1 − p)μ2) is also a stationary distribution for any real number 0 ≤ p ≤ 1. How ...
1
vote
0answers
33 views

Reading material on Random Walk on S_n using Transpositions

I am from an engineering background and I wanted to get hold of some very basic reading material on Random Walk on $S_n$ (symmetric group on n letters) using Transpositions. Could someone suggest ...
0
votes
0answers
34 views

Probability distribution for a random walk in arbitrary dimension

I'm trying to find the probability distribution for a random walk on a lattice with lattice constant a in arbitrary dimension d. The rules for my walk is that in each step the walker has to move to an ...
0
votes
0answers
24 views

How to get more profit in stochastic process?

Suppose there is a system, for each step, I cost something but I didn't know how much I cost, and the system return to me something, which follow Guassian distribution and the expectation is what I ...
2
votes
0answers
36 views

An inequality for symmetric random walk

I need to show that if $(X_j)$ are symmetric i.i.d. random variables with partial sums $S_n:= \sum_{j=1}^n X_j$, then for all $x \geq 0$ $$P(|S_n| > x) \geq \frac{1}{2} P(\max_{1 \leq j \leq n} ...
0
votes
0answers
30 views

Final step of a random walk proof

I am working through the last bit of a random walk proof to show that a 3-d random walk is transient. The result I am looking for states that: $\frac {1}{2}^{2s} {{2s}\choose{s}} \sum_{j+k\leq{n}} ...
1
vote
0answers
40 views

Expected time of reaching 0 of a simple symmetric random walk

Consider the symmetric, simple random walk on $S = \{0, 1, \ldots , k\}$ for $k \in \mathbb N$. Let $$T = \min \{ n \in \mathbb N_0|X_n = 0\}$$ be the first time where the process reaches $0$ and ...
2
votes
0answers
48 views

2d random walk on the nonnegative quadrant using martingale techniques

I know the basics of (discrete time) martingales, and I'd appreciate any help and suggestions on how to prove the following using martingale techniques. Let $Z_n$, $n\ge 0$ be a random walk on the ...
0
votes
1answer
76 views

Probability that random walkers meet

I was wondering about a question about Random Walks. I came across various papers where the probability of 2 random walkers in 1 dimension and 2 dimension starting at the same point and returning to ...
2
votes
1answer
58 views

Random walks : Hitting and recurrence Times relation

I have trouble understanding that how $$E\left[T_0|X_{0} = 0\right] = 1 + E[H_0|X_0=1] $$ where $T_0 = \inf\{n \geq 1:X_n = 0 \}$ and $H_A =\inf\{ n\geq 0: X_n \in A \}$. In other words $T_0$ is the ...