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

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
75 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
63 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
57 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
28 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 ...
1
vote
1answer
78 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
137 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
145 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
85 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
58 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
403 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
93 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
152 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
219 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
67 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
132 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
62 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
100 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
128 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
57 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
83 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
179 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
217 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
197 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
82 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
212 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
79 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
595 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
117 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
0answers
111 views

Extracting hitting times from the pseudoinverse of a Laplacian matrix for an undirected graph

Provided a pseudoinverted Laplacian matrix for an undirected graph $G$, how can I extract first passage and commute times between vertex pairs in $G$?
1
vote
1answer
173 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
53 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
187 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
198 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
178 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
2answers
265 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
116 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)$?
1
vote
0answers
254 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. ...
2
votes
0answers
158 views

Random walks in $1$, $2$ and $3$ dimensions [closed]

I know that this may seem easy but I have no clue where to start (if possible could you answer this in the simplest way possible)? Consider a person who is at the position $x=0$ on the $x$-axis at ...
1
vote
1answer
58 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
144 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
130 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
217 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
402 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
364 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
393 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
137 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
204 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
152 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 ...
4
votes
0answers
126 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 ...