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
97 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 ...
41
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
172 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
107 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
87 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
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 ...
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
114 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
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 ...
4
votes
2answers
181 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
92 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
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 ...
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
120 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
180 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
286 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
96 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
159 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
75 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
106 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
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 ...
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
1answer
115 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 $. ...
1
vote
1answer
356 views

Random walk serial correlation

Given a model $$Y_t =b_0 + b_1 \cdot X_t + b_2 \cdot Z_t + e_t,$$ where the error term $e_t$ follows a random walk form of serial correlation $e_t = e_{t-1} + u_t$. Further assume $u_t$ has zero mean ...
2
votes
1answer
369 views

Proof: Mean and Variance of the squared distance of a random walk in n-dimensional space

consider a $x$ step random walk starting from origin in $n$-dimensional space where each step is taken into a random direction and has a distance of 1, i.e., each step is a vector on the ...
1
vote
1answer
291 views

A Boundary crossing result for discrete brownian bridge

Let $S_n$ be a random walk with gaussian increments with $S_0=0$, i.e. $S_n-S_{n-1}\sim N(0,1), n\geq 1$. Fix $a>0,b\in \mathbb{R}$ and $c<a+bn$. Define the new process $$ ...
1
vote
1answer
99 views

Help calculating variance of a random variable

This is related to this question Average end point of 1-dimensional random walk? Given several discrete random variables such that $p(Z_i=1-2k)=p$, where $k$ is a small real number, and ...
2
votes
1answer
384 views

Mean displacement for a random walk on a $d$-dimensional lattice

How does the mean displacement of a random walk on a $d$-dimensional integer lattice (or $d$-dimensional hexagonal lattice) scale with the number of steps $N$ in the walk? Is the displacement always ...
0
votes
1answer
116 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
2answers
932 views

Random walk with absorbing barriers

Consider a random walk with absorbing barriers at $0$ and $3$. $\mathbb P(S_{n+1}-S_n=1)=0.6$ and $\mathbb P(S_{n+1}-S_n=-1)=0.4$. What is the probability of eventual absorption at $0$, given that the ...
4
votes
2answers
144 views

Prove that a random walk on $\mathbb{Z}_+\cup \{0\}$ is transient

Prove that a random walk on $\mathbb{Z}_+ \cup \{0\}$ is transient with $p_{i,i+1}=\frac{i^2+2i+1}{2i^2+2i+1}$ and $p_{i,i-1}=\frac{i^2}{2i^2+2i+1}$. So since this Markov chain has only a single ...
1
vote
1answer
254 views

Cover Time for Random Walk on a cycle

I'm trying to find the expected time to cover all $N$ nodes on an undirected cycle graph, starting from a given node $k$. The probabilities of moving clockwise and anticlockwise are $\frac{1}{2}$ ...
1
vote
0answers
69 views

planar walks and catalan numbers

prove that following numbers are equal: (unordered) pairs of lattice paths with n+1 steps each, starting at (0,0), using steps (0,1) or (1,0), ending at the same point and only intersecting at the ...
4
votes
1answer
339 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? ...
0
votes
1answer
353 views

Simple Probability Matrix

Consider a simple model that predicts whether you pass you next test or not based on the result of your previous test. If you pass your previous test, then you have 0.2 chance you will pass your ...
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 ...
0
votes
3answers
1k views

The variance of a simple random walk/process

I've been trying to wrap my head around this for the past day. Please help! Let $\epsilon_i = \pm 1$ with equal probabilities independently for $i=1,...,N$. Then $Z_i = \epsilon_1 + ... + \epsilon_i$ ...
0
votes
1answer
118 views

The random walk $S_n=a+\sum_{i=1}^nX_i$

Consider a variant of random walk defined as $$S_n=a+\sum_{i=1}^nX_i,$$ where $X_i$ takes either value $2$ with prob= $p$ or value $-1$ with prob =$1-p$. What is $P(S_n=b)$?
2
votes
1answer
458 views

Random walk, Cat and mouse

Here is the problem. In graph G, on different vertices there is cat and mouse. Cat and mouse do independent random walk, but time is synchronous, in one unit of time both cat and mouse do one step. ...
1
vote
1answer
60 views

Inequality between two Random Walks

Let's consider two Random Walks, $$x^{(1)}_t = x_0 + \sum_{i=1}^{t}\xi^{(1)}_i,$$ $$x^{(2)}_t = x_0 + \sum_{i=1}^{t}\xi^{(2)}_i.$$ The random variables $\xi^{(1)}_i$ are i. i. d. They take values on ...
3
votes
1answer
153 views

A Coupled Random Walk on the xy-Plane

Consider a point on the $xy$-plane whose position is updated in iterations. In each iteration, the point undergoes, with equal probability, either an $A$- or a $B$-update, defined as follows: ...
3
votes
1answer
157 views

successive doubling the stake until head appears

I consider the following gaming system: Start with 1 dollar and always bet on head (coin tossing). You always double your stake until the first head appears. Maximum rounds: $n$ I formulated it as a ...
1
vote
1answer
375 views

Asymmetric random walk with unequal step size other than 1.

Say, an asymmetric random walk, at each step it goes left by 1 step with chance $p$, and goes right by $a$ steps with chance $1-p$. (where $a$ is positive constant). The chain stops whenever it ...
0
votes
1answer
707 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 ...
1
vote
2answers
645 views

Probability related to random walks in two dimensions

I'm trying to show that two random walks will eventually meet in a two dimensional setting but I can't figure out where to start. Can someone lead me towards the right direction?
4
votes
2answers
569 views

Random walk on lollipop graph

Hi i am trying to prove expected Hitting time on the Lollipop graph. It is a graph on $n$ vertices with clique on $n/2$ vertices and path joined to this. Let vertex $i$ be a vertex on the clique, ...
1
vote
1answer
143 views

How to solve recurrence in two variables

How can you solve this simple looking recurrence relation in two variables? $f(a,b) = 1 + \frac{a f(a+1,b+1) + (x-a)f(a+1,b)}{x}$ The function $f$ is defined for non-negative integer values $a$ and ...
0
votes
2answers
270 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, ...
1
vote
1answer
207 views

Random Walk probability game

I try to solve some exercises from olympiads and I have difficulties with this one: Consider a round table with 20 people. One of these players receive a book and chooses one of his neighbors and ...