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
0answers
10 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
0answers
12 views

Consider a random walk where $p \neq 1/2$, where the starting point is random and has a binom distn. Find the probability of absorption at $N$.

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
18 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
42 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
23 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
26 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
47 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
37 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
59 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
28 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
44 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
32 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
280 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
32 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 ...
0
votes
0answers
11 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 ...
-2
votes
0answers
49 views

Random walk of a bishop [on hold]

If an erratic bishop starts at bottom left of a chessboard and performs random but legal moves (all with equal probability and independently of earlier moves) and $X_n$ is the positon after $n$ moves, ...
1
vote
1answer
15 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
31 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
0answers
14 views

implication of positive speed of random walk on a graph

Let $(V,E)$ be a vertex-transitive graph and let one vertex be the origin. Let $d(v,0)$ be the graph distance between $v$ and $0$. Consider $(X_n)$ a simple random walk on the graph. Let $A_n$ be the ...
1
vote
1answer
26 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
16 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
28 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
23 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
71 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
37 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
355 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
130 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
27 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
28 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
35 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
29 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
75 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
57 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 ...
0
votes
1answer
29 views

How to calculate the correlation coefficient of two independent random walks to demonstrate spurious regression?

I heard of non-stationary time series could result in spurious regression, so I want to know, as sample size goes to infinity, how to calculate the correlation coefficient of two descrete independent ...
0
votes
0answers
28 views

A random walk with an exit

Let's consider a random walk. We start on the tile $n_0$. For our $q$th step, if we're already on the tile $k$ then we have a probability $P_{q,k,p}$ to go to the tile $p$ with $p\in\mathbb{N}$. ...
1
vote
1answer
50 views

Show expectation is finite of an asymmetric walk

Where does this result come from? $$\mathbb{E}\left[\left(\frac{q}{p}\right)^{S_n}\right]\leq \left(\frac{q}{p}\right)^n + \left(\frac{q}{p}\right)^{-n}$$ where $$S_n = \sum_{i=1}^{n}X_i$$ and $0\leq ...
0
votes
1answer
29 views

Series of random numbers on a continuous function

At one point, I read about a function used to generate random numbers that follow a continuous pattern. By this I mean random numbers that as a series is random, but in which items tend to be ...
0
votes
0answers
38 views

Expected number of returns by time n in a symmetric 1-d random walk?

How do we prove that $E(N_{2n})=(2n+1){{2n}\choose{n}}(\frac{1}{2})^{2n}-1$ I started working on it. And I see that $E(N_{2n})=\Sigma_0^n{{2k}\choose{k}}(\frac{1}{2})^{2k}-1$ Therefore the problem ...
1
vote
0answers
30 views

capacity of biased random walk in $\mathbb{Z}^2$

Let $P_{x,y}$ the probability that a random walk starting from $x$ will ever visit $y$. Consider a biased random walk in $\mathbb{Z}^2$. Let $A_k$ be the set of vertices having a distance less than ...