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

learn more… | top users | synonyms

9
votes
0answers
118 views

Expected range of simple random walk in $\mathbb{Z^2}$

Let $(Y_k)_{k\geq0}$ be a simple random walk process. The range of an $n$-step random walk, $R_n$, is a random variable that characterizes the number of distinct points visited at time $n$: ...
7
votes
0answers
276 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, ...
6
votes
0answers
64 views

Probability on entering direction of a simple random walk

Let $X(n)$ be a simple random walk on $\Bbb{Z}^2$. Also we define $S_{R} = \inf\{n > 0 : X(n) \notin [-R, R]^2 \} $ : the exit time of the square $[-R, R]^2$, $T_{v} = \inf\{n > 0 : X(n) = ...
5
votes
0answers
64 views

Standard deviation of a quantum walk?

The standard deviation of a classical random walk with $n$ steps is $\sqrt n$ - Standard deviation of a random walk. I have read in many places that the standard deviation of a quantum walk $n$ with a ...
5
votes
0answers
165 views

Intuition for the optimality of bold play

There is a standard result (I think originally by Dubins and Savage) that if one wants to maximise the probability of winning a certain amount in an unfair game of chance then an optimal strategy is ...
5
votes
0answers
231 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 ...
4
votes
0answers
41 views

Discrete Time Two sided Gaussian Random Walk : Hitting Time Distribution

I am looking at the hitting time of a two sided Gaussian random walk i.e. $S_{n}=\sum_{i=1}^{n}X_{i}$ where $X_{i}$ are i.i.d normally distributed random variables. The hitting time is ...
4
votes
0answers
37 views

Random walks and their uses

Can anyone provide some motivation behind the use of random walks? I know they're used a lot in computer science, in things like page walk (I think that's what it was called- something like pagerank), ...
4
votes
0answers
98 views

Uniform integrability of the maximum of a random walk with negative drift

Given $S_k^{(n)} = X_1^{(n)} + ... + X_k^{(n)}$ for all $k,n\in\mathbb{N}$, where the $X_i^{(n)}$'s are iid with mean $-\gamma$ for some $\gamma > 0$ and unit variance. Let ...
4
votes
0answers
232 views

Random walk on $\mathbb{Z}$ with more than two possible steps

Let be $\{X_n\}_{n\in \mathbb{N}}$ random walk on $\mathbb{Z}$. Let be $$P(X_{n+1} = k + a| X_n = k)= p_a$$ for $a\in \mathcal{A} \subset \mathbb{Z}$. Let say that $X_0 = 0$. I am interested in ...
4
votes
0answers
68 views

random walk on real line

Suppose I start at $A>0$ and every period I either move a distance $B$ to the right with probability $p$ or a distance $C$ to the left with probability $1-p$. The expected move is positive: ...
4
votes
0answers
147 views

Conditional probability and integrating out part of a random walk

Suppose that I have a random walk process defined by $\alpha_{t+1}$ ~ N$(\alpha_t, \omega^2)$. Given $\alpha_t$ and $\alpha_{t+2}$, I understand why the conditional formula for ...
4
votes
0answers
132 views

probability of this event happening

Play $(n+1)t$ rounds of the same coin-tossing game and the coin is fair ($n$ is a fixed natural number). Please help me find the following probability: $P$(the number of rounds of tossing that ...
4
votes
0answers
110 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 ...
3
votes
0answers
22 views

Random matrices, eigenvalue distribution.

I just investigated randn(1024) + 1i*randn(1024), a 1024x1024 complex valued matrix with elements both real part and imaginary part drawn from $\mathcal{N}(\mu = 0, \sigma = 1)$. I was a bit surprised ...
3
votes
0answers
58 views

Simple random walk conditioning on non-return

Consider a simple symmetric random walk on $\mathbb{Z}$, $(S_t)_{t \geq 0}$, with $S_0=0$. Let $k$ and $j$ be two positive integers. Let $P_{k,j}$ be the probability that the walker hits the vertex ...
3
votes
0answers
41 views

Self-avoiding random walk on $\mathbb{Z}^2$ getting stuck

Let $W_n$ be a self-avoiding random walk (SAW) on $\mathbb{Z}^2$, starting at the origin. Formally, $W_0=0$ and for $n\ge 0$, $W_{n+1}$ is chosen uniformly from the neighbours of $W_n$ which were not ...
3
votes
0answers
79 views

Sum of sequence of random variables infinitely often positive

Let $X_1,X_2,\ldots$ be an infinite sequence of independent (but not necessarily identically distributed) random variables with $E(X_i)=0$ for all $i$. Set $S_n=\sum_{i=1}^n X_i$. I want to show that ...
3
votes
0answers
80 views

Expected minimum of a finite random walk.

So I couldn't find any resource for how to calculate the expected minimum of a random walk. Since it is such the minimum of the random variables are actually not independent as they are cumulative ...
3
votes
0answers
34 views

Number of times above a linear boundary for a finite variance random walk

I consider a random walk $(S_n)$ with mean zero and finite variance, and $\epsilon>0$. Is it true that $$ \mathbb{E}\left[\sum_{n=0}^{+\infty} 1_{S_n>n\epsilon}\right] < +\infty \quad ? $$ ...
3
votes
0answers
58 views

Upper bounds on the sum in a Martingale process

My question is related the hitting time of not a random walk, but a more general martingale process. Suppose we start with an arbitrary $x_0=x$ with $0\leq x\leq 1$. We compute $x_{t+1}$ from $x_t$ ...
3
votes
0answers
71 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 ...
2
votes
0answers
27 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. ...
2
votes
0answers
35 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 ...
2
votes
0answers
31 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 ...
2
votes
0answers
37 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} ...
2
votes
0answers
50 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 ...
2
votes
0answers
22 views

Estimating the discrete laplacian to prove recurrence of simple random walk for d=2

Given a function $f : \mathbb Z\times \mathbb Z \rightarrow \mathbb{R}$ we define the discrete laplacian of $f$, $\triangle_df$, by the following rule $\triangle_df(x,y)= \dfrac{f(x + 1, y)+f(x, y + ...
2
votes
0answers
35 views

Sum of $\{X_n\}$ iid random variables contained in a compact interval implies each $X_i=0$ a.s.?

I am working through an exercise that starts with a sequence i.i.d. random variables where for $a\leq b$, $$\Pr\left(\lim\sup_n \sum_{i=1}^{n} X_i \in [a,b] \right) \neq 0.$$ Does this require $X_i ...
2
votes
0answers
30 views

Comparing hitting time of two random walks

There are two random walks, $S^t_i=S^{t-1}_i+ X_i^t$ for $i=1,2$, $X^t_i$ i.i.d they have boundaries $h_1$ and $h_2$ respectively. I'm wondering if it's possible to calculate the probability that one ...
2
votes
0answers
83 views

Hitting time of a maximum of random walk converges to that of Brownian motion

Suppose $S_n$ is a simple random walk; formally, $S_n=\sum_{i=1}^n X_i$ for $X_i\sim\mathcal{U}(-1,1)$, i.i.d.. Denote by $M_n$ the maximum of the random walk on $n$ steps; formally, $M_n=\max_{0\le ...
2
votes
0answers
47 views

Recurrence for a random walk question

Let $X_i$'s be iid and define $X_1+\ldots+X_n=S_n$. I was trying to show that if $S_n$ is recurrent, then $S_{2n}$ is also recurrent. Assume these walks are in $\mathbb{R}^d$. Using Chung-Fuchs ...
2
votes
0answers
49 views

The number of paths, which touches or crosses the abscissa

If $S_n$ is a random walk s.t. $S_0=1$. $S_n=X_1+X_2+...+X_n$ for $n\ge 1$ and for any $i\in N$ $P[X_i=1]=P[X_i=-1]=1/2$ for $r\ge 1$ calculate the number of paths from time $0$ to $2n-1$ ...
2
votes
0answers
74 views

Random Walk Return Probabilities – Is there an intuition to understand them?

Every mathematician is familiar with the result (due to Pólya) that for a random walk in a $d$-dimensional lattice, the probability $p(d)$ for returning to the origin eventually is $1$ if $d=1,2$, but ...
2
votes
0answers
56 views

A random walk on the unit distance graph in $\mathbb{R}^n$

Define a graph $G_n$ whose vertices are the points in $\mathbb{R}^n$ with an edge connecting any two points that are one unit apart. Such a graph is called the unit distance graph in $\mathbb{R}^n$. ...
2
votes
0answers
69 views

Random walk with $\sum_{n=1}^{\infty} \frac{1}{n} \mathbb{P}\{ S_n > 0 \} < \infty$

Consider a random walk started at $S_0=0$, denoted $S_n = \sum_{k=1}^{n}X_k$, where $X_1$, $X_2$... are the i.i.d increments. If we have $\sum_{n=1}^{\infty} \frac{1}{n} \mathbb{P}\{ S_n > 0 \} ...
2
votes
0answers
52 views

Expectation of a Random Walk

I am researching Random Walks and trying to find how to get their expectations. I have studied Markov chains before. I have found one way of getting the expected number of steps to reach a state by ...
2
votes
0answers
62 views

mean displacement inequality for random walk with drift away from zero

Suppose $X_n$ is a nearest neighbor random walk on the integers with transition probabilities biased towards moving away from zero but with the bias asymptotically vanishing as you move away from ...
2
votes
0answers
146 views

Finding functions where the increase over a random interval is Poisson distributed

I'm trying to construct a type of function $f(t_1, t_2)$ that counts the number of deterministically simulated Poisson events between two points in time. We can use a single valued function ...
2
votes
0answers
45 views

Sums of independent random variables

I was unsuccessful in deriving a good estimate of the distance below. Let $(X_{n})_{n \geqslant 1}$ be a sequence of i.i.d. random variables, and let $(\varepsilon_{n})_{n\geqslant 1}$ be a sequence ...
2
votes
0answers
105 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
0answers
64 views

Random walk type problem with time increments

Imagine you have $\$50$ and every $2$ minutes you either gain or lose $33$ cents. How would you model the evolution of the hypothetical bankroll for the next hour? My approach based on what i've read ...
2
votes
0answers
63 views

Dimension free Concentration bounds for Martingales

Consider the following random process which is defined on $n$ numbers $0\leq x_1,\ldots,x_n\leq 1$: At each step, pick an arbitrary number, say $x_i$. Then randomly (and independently) change its ...
2
votes
0answers
316 views

Teleporting random walk

Given a directed graph $G = (V,E)$, to define a random walk on $G$ with a transition probability matrix $P$ such that it has a unique stationary distribution (as mentioned in this paper) I used a one ...
2
votes
0answers
116 views

Spectrum of Transition Matrix for Random Walk

Consider the symmetric random walk on $\{0, 1, \dots, n\}$ with transition probabilities $P(j \to j \pm 1) = 1/2$ for $1 \le j \le n-1$ and $P(0 \to 0) = P(0 \to 1) = P(n \to n) = P(n \to n-1) = 1/2$. ...
2
votes
0answers
105 views

Equilibrium distributions for a finite urn scheme

Given an urn with $n$ (fixed) balls that can be red or black, and given two parameters $0 < p, \, q < 1$, keep doing the following: Flip a $p$-coin. If heads come up, remove a black ball or ...
2
votes
0answers
128 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 ...
2
votes
0answers
307 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 ...
2
votes
0answers
252 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
30 views

Autocorrelated, discrete, bounded and symmetric random walk with no edge attraction

I need to move over a discrete set of linearly organized.. let's say "Japan steps" $S=\{0,\dots,c\}, c \in \mathbb{N}^*$. My current position is given by $d \in S$. On each time step, I need to draw ...