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
1answer
36 views

Bounding the number of visits for each site of a random walk by a sequence

Recently, I asked if, for each $k>1$, a transient random walk visits each site less than $k$ times a.s.. You can find the question here: Visits from a transient random walker on the integers This ...
2
votes
1answer
76 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 ...
3
votes
2answers
86 views

Random walk on one-dimensional lattice - understanding the expression $pe^{i\theta} + qe^{-i\theta}$

I've started reading the book - First Steps in Random Walks and in the very first example in Chapter 1 they talk about a random walk on a one-dimensional lattice. If we consider a particle starting ...
1
vote
2answers
62 views

For a Gaussian Random walk where $x_n$ is the sum of $n$ normal random variables, what is $P(x_1 >0, x_2 >0)$?

I know that the events $x_1 >0$ and $x_2 >0$ are not independent, but I can't think of a way to find a conditional probability so I can solve this. Thanks!
0
votes
1answer
121 views

Recurrence for dependent random walks.

Let $\{X_i\}_{i\in\mathbb{N}}$ be a sequence of random variables taking values in $\{\pm e_1,\pm e_2\}$, where $\{e_1,e_2\}$ is the standard basis of $\mathbb{R}^2$. If $\{X_i\}$ are i.i.d. ...
2
votes
1answer
115 views

Martingales of random walk

Let $S_n$ be a random walk process defined by $$S_n=X_1+\dots+X_n$$ with $X_i \sim N(\mu,\sigma^2)$ and $X_i$ are i.i.d. I'm trying to prove that the quantity $(S_n-n\mu)^2-n\sigma^2$ is a ...
5
votes
2answers
155 views

How can we directly see that the number of random walks starting and ending at the origin is ${n\choose n/2}^2$?

In an infinite two-dimensional square-shaped grid, we define four directions, north, south, east, west. We thus have $4^n$ random walks of length $n$. If we end where we started, for every north step ...
7
votes
1answer
171 views

Recurrence of a certain class of $2$-$d$ random walks

As is well known, a symmetric random walk on $\mathbb{Z}^d$ (the lattice of $d$ dimensional vectors with integer components) is recurrent if and only if $d=1,2$. In particular it is transient for ...
2
votes
0answers
46 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 ...
1
vote
0answers
65 views

Random Walk in confined region and loop configurations

Suppose I take a random walk on a 2 dimensional square lattice, but this lattice plane has a finite size, e.g. Dx*Dy. I can not cross the boundary, my step length is the lattice cell size, I either go ...
0
votes
1answer
168 views

Solving a differential equation (Lattice Laplacian)

Suppose that $ p_n(t) $ is the probability of finding n particle at a time t. And the dynamics of the particle is described by this equation : $$ \frac{d}{dt} p_n(t) = \lambda \Delta p_n(t) $$ ...
12
votes
1answer
299 views

Random walks and diffusion limits

Imagine a long and narrow cylinder of radius r and a point particle that moves in the region bounded by the cylinder. The motion is specified as follows: starting at a point on the inner wall of the ...
3
votes
3answers
103 views

A fly on a triangle?

A fly is on the vertex of a triangle. It can move left with probability $\frac 12$ and right with probability $\frac 12$. What is the expected number of moves till it reaches its starting point? ...
1
vote
2answers
247 views

Calculating expected value of random walk with one stop value.

I know that for a random walk with two stop values, the expected value of the number of steps needed is $ab$ where the stop values are $-a$ and $b$ and the initial position is at 0. What about for ...
1
vote
2answers
75 views

Random Walk with Edges

The setup for the specific problem that led to this question is as follows: You are playing a game at a casino and have \$10,000; The bank has \$2,000. You are making \$1,000 bets, with a equal ...
2
votes
1answer
754 views

Expected time for winning in biased Gambler's Ruin

Consider the random walk $X_0, X_1, X_2, \ldots$ on state space $S=\{0,1,\ldots,n\}$ with absorbing states $A=\{0,n\}$, and with $P(i,i+1)=p$ and $P(i,i-1)=q$ for all $i \in S \setminus A$, where ...
1
vote
0answers
138 views

Bayesian random walk

Suppose that, at first, I am trying to estimate the mean and standard deviation of some data that I assume to be normally distributed. My prior is gaussian with mean $\mu_0$ and variance $\sigma^2_0$. ...
0
votes
3answers
172 views

Probability of having X more heads than tails for N tosses.

Giving a a fair coin, and tossing it N times, in how many possible outcomes would there be a point wherein there were more heads than tails tossed, ie, net heads.
1
vote
1answer
54 views

Concerning the distribution of a random variable of a random walk that doesn't make any sense to me

Let $\Omega = \{w = (x_1, \dots, x_N) | \; x_i \in \{-1, 1\}\}, \;X_k(w) = x_k, \;S_n(w) = \sum_{k=1}^n X_k(w), \; S_0(w) = 0.$ After having proven a few theorems about $S_n$, in our lecture about ...
1
vote
0answers
135 views

Brownian motion, rate of large events

Given the most simple brownian motion: $$ \dot x(t) = \sigma \eta(t)$$ where $\langle \eta(t)\eta(t')\rangle=\delta(t-t')$, I define as large event in a time-frame $\tau$ a portion of the trace ...
1
vote
0answers
144 views

Stopping time and martingale for random walks

Let $X_0=0, X_1, X_2,\dots, X_N$ be i.i.d. random variables, with Gaussian distribution $\cal N (0,1)$. For $k=0,\dots, N, S_k=\sum_{i=1}^k X_i$ and $\tau=\min\{k:S_k^2\geq N-k\}$. So $\tau$ is a ...
1
vote
0answers
51 views

Random walk - proving limits exist

Consider the random walk $\{X_k\}_{k\geq0}$ on $\mathbb{Z}$ with transition probabilities $$\begin{cases} p_{i,i-1} = p_{-1} &> 0 \\ p_{i,i+1} = p_{1} &> 0 \\ p_{i,i+2} = p_{2} ...
2
votes
1answer
87 views

What is the probability that the robot steps on the bomb?

Suppose a robot is initially placed at $0$ on the number line, and is programmed to take steps of integer length in the positive direction between $1$ and $k$, inclusive, where $k$ is a positive ...
2
votes
3answers
292 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$, ...
3
votes
1answer
320 views

Probability of being at a certain point after $N$ steps in Random Walk with a single absorbing barrier

A random walker in $1$ dimension starts walking from a point $k>0$ with an absorbing barrier at point $0$. What is the probability that he will reach a point $m>0$ in $N$ steps? How should I ...
2
votes
0answers
108 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
1answer
99 views

law of large number modified statement

The weak law of large number states that, given $Y_n = \sum_{k=1}^{n} X_k$, where $X_k$ are random variables independent and identically distributed with finite expectation $\mu$, $$ \forall ...
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: $$ ...
0
votes
0answers
184 views

On the second derivative of Wiener process

As we all know, continuous white noise is the derivative, with respect to time, of a Wiener process. My question is that does the second derivative of Wiener process exists? If so, what is it and how ...
2
votes
1answer
108 views

Computation of a mean (random sum)

Let $X_1$, $X_2$, ... be independent and identially distributed positive random variables and define the sum $S_n = X_1 + X_2 + ... + X_n$. Consider the first time $N$ where $S_N \ge b$ with a given ...
2
votes
1answer
89 views

A continuous random walk of length 1

Suppose one starts at origo in in the plane and takes $N$ steps of length $1/N$ in a random direction, what is the distribution of the resulting distance from origo as $N$ approaches infinity? For one ...
1
vote
1answer
81 views

Absorbing state for a collection of random walks

Further to this question; having learned some stuff since I posed it. Consider a collection of random walks $X_i$ which take finite integer values. These evolve as time-inhomogeneous Markov Chains. ...
1
vote
2answers
61 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 ...
0
votes
0answers
29 views

What random process is this?

This is a rather basic question, is just that I don't know a thing about this subject. Let's say $x$ is an integer. At $t=0$, the value of $x$ is 1. Then, at each time step, one of the following ...
2
votes
1answer
118 views

Number non self avoiding closed walks surrounding some point

While studying some Peierls-like arguments in statistical physics I thought about the following problem: We have some 2d-integer lattice like this, for simplicity infinite in all directions. Now fix ...
5
votes
0answers
168 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 ...
4
votes
2answers
188 views

Speculating on the stock exchange

Imagine you model each stock as a random walk (fractal) and also that you can buy and sell at any price. Suppose also that it 'walks' with the pace of 1. If you buy, for example, 1000 shares of ...
0
votes
1answer
95 views

When is an infinite sequence of integers purely deterministic with no randomness involved?

I see in literature very different descriptions of what is a deterministic system such as: "... a system in which no randomness is involved in the development of future states of the system...>>>" I ...
2
votes
0answers
65 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 ...
4
votes
1answer
1k 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 ...
1
vote
1answer
123 views

Arguing on stopping time probability

Consider the random walk where $X_t=\sum_{i=1}^t Y_i$, $Y_i$s are iid and take $\pm$1 with probabilities $p$ and $1-p$ respectively, where $0<p<0.5$. Define stopping time ...
1
vote
0answers
191 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
294 views

Coin toss probability calculation

A gambler bets on coin flips. With each flip, he wins $1$ dollar with probability $p$, and loses $1$ dollar with probability $1-p$. He starts with $2$ dollar and stops when he reaches either $0$ or ...
2
votes
2answers
106 views

Ties in Matching Pennies

Players A and B match pennies N times. They keep a tally of their gains and losses. After the first toss, what is the chance that at no time during the game will they be even? I have seen a solution ...
1
vote
1answer
169 views

Random walk probability non-symmetric steps

I currently have a probability class tutorial question that I have no idea where to begin. At first instinct, I thought it may have been a CTMC question or branching question, but now I have no idea, ...
2
votes
1answer
76 views

Random walk - Solution verification

A particle moves randomly 2n times. Each time it chooses one direction: north, south, west, east with even probability and without effect from previous choices, it then moves one step in that ...
1
vote
1answer
110 views

Flipping an unfair coin

An coin has probability $p<0.5$ of landing heads up. We flip it infinitely many times, after $n$ tosses, let $S_n$ be the number of heads minus the number of tails. What is the expected value of ...
4
votes
0answers
148 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 ...
2
votes
0answers
73 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
1answer
121 views

An application of Donsker's theorem.

Let ${X_i}$ be iid with $E[X]=0$ and $Var(X)=\sigma^2$ Let $S_0=0$ and $S_n=X_1+...+X_n$ for all $n \ge 1$. Show that $\lim_{n\rightarrow \infty}P(S_k>0 \space for \space k=n,n+1,\dots,2n)=1/4 $. ...