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

learn more… | top users | synonyms

0
votes
0answers
15 views

Deducing results about continuous time random walks from the corresponding discrete time result

Is there any standard way to prove results about continuous time random walks from the corresponding results for discrete time random walks? Specifically, my problem is that I was reading Lawler and ...
0
votes
0answers
22 views

Find the Probability random walks hits $b$ before $c$ before $a$

Define $$\tau_{x} := min\{k\geq0 : S_{n}=x\}$$ And let $a,b,c \in \mathbb{Z}$ such that $a<b<0<c$ and $S_n$ is a random symmetric walk starting at 0. Find ...
1
vote
0answers
26 views

Cicurlar random-walk.

Suppose you have a computer network with 5 code as following. Packet can arrive at any node and any other node can be its destination equal uniform probability. Determine the average number of ...
0
votes
0answers
24 views

Random-walk in a pentacle (5 nodes)

There are a total of 5 nodes at the edge of a pentagram At each node, you have a 4 choices which will lead you to either a destination node or non-destination node. Assume the decision of path is ...
1
vote
0answers
49 views

Couple/Compare two stochastic processes and prove an intuitive proposition

Consider a stochastic process (denoted $X$) $X_0, X_1, X_2, \ldots$ (not necessarily a Markov Chain) over state space $\{0, 1, \cdots, n \}$. The transition probabilities are $$P(X_{i+1} = 1 \mid ...
0
votes
0answers
10 views

Simple Random Walk; Proof hitting theorem; Ballot Theorem

Suppose that $(X_{n}:n\in\mathbb{N})$ is a $\pm1\mbox{-valued sequence.}$ Let $p\in(0,1)$ and $p=\mathbb{P}(X_{i}=1)\mbox{ and}\mathbb{P}(X_{i}=-1)=1-p=q$ . Define the simple random walk ...
1
vote
0answers
53 views

Probability of going to the origin in a random walk

Been given this as practice for my Stochastic Processes course. I'm fairly new to the concept, so I haven't been exposed to a general method. Any hints/tips for the following? A gambler plays a ...
3
votes
0answers
63 views

Duration of a Gambler's Ruin game against an opponent with infinite credit

A gambler enters the casino with $x\$$ in his pocket and sits on some table. At each iteration he bets $1\$$ and either wins $1\$$ with probability $p\leq\frac{1}{2}$ or loses $1\$$. Assuming that ...
2
votes
1answer
70 views

Showing that lim sup of sum of iid binary variables $X_i$ with $P[X_i = 1] = P[X_i = -1] = 1/2$ is a.s. infinite

Let $(X_i)_{i\in\mathbb{N}}$ be an i.i.d. sequence of binary random variables with $$P[X_i = 1]=P[X_i = -1] = \frac{1}{2}$$ and let $$S_n = \sum_{i=1}^{n} X_i.$$ I'd like to show that $$P[\lim ...
1
vote
1answer
66 views

Probability- Coin Flipping Game

If you play a game where you flip a coin if it lands heads you win £1 and tails you lose £1.If you start with $£K$ what is the probability that you are bankrupt after $n$ games? MY ATTEMPT I ...
2
votes
1answer
62 views

Expected number of moves of a random walk inside a simplex

Few days ago, Roger Blazey, retired head maths teacher, at LinkedIn group told about the following problem: “This problem was raised as part of a lecture at The Biennial AAMT (Australian ...
1
vote
0answers
36 views

Bound on sum random variables and Martingales

Suppose $X_n=q$ with probability $p$, and $X_n=-p$ with probability $q$ where $p+q=1$. Prove that for every $n$, the probability that $S_k\geq b$ for any $k$ as $1\leq k \leq n$ is at most ...
0
votes
1answer
59 views

Expectation of hitting time for simple symmetric random walk

Assume there is a simple symmetric random walk $$S_n=X_1+...+X_n,\quad S_0=0$$ where $\mathbb P(X_i=\pm 1)=\frac{1}{2}$. Define $T=\inf\{n:S_n=1\}$. How to compute $\mathbb E(T)$? My idea: if ...
0
votes
0answers
43 views

Maximum time-to-exit of random walk in R^n

I am trying to solve the following problem : Given a set $A$ in $\mathbb{R}^n$ and a point $p$ , I want to find a convex subset of $A$, call it $C$, such that $p$ is in $C$ and random walk starting at ...
1
vote
0answers
31 views

better expression for simple random walk

Let $P_{k,j}$ be the probability that the probability that simple symmetric random walk starting from the origin reaches the point $k \in \mathbb{N}$ precisely in $j$ steps without ever returning to ...
1
vote
1answer
65 views

A question about independence of sigma algebras (generated by random variables)

Let $X_1, X_2, \ldots$ i.i.d random variables. Is it possible that $$\{X_{n+1} \in B\} \in \sigma({X_1, \ldots, X_n})$$ for some $B$? Why yes/not? I want to show that $\sigma(X_{n+1})$ and ...
2
votes
0answers
20 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 + ...
0
votes
0answers
23 views

continuous random walks, wiener process, ito process: “snowballing” for high enough volatility?

I'm finishing a project for my ODE class and ran into some strange behavior involving a SDE (not exactly sure how to say this, but...) generated by an Ito process, using the Wiener process. I guess ...
1
vote
1answer
44 views

Brownian motion is almost surely continuous

Why is Brownian motion required to be almost surely continuous instead of merely continuous? For example, this is stated as condition 2 in this article in section 1, Characterizations of the Wiener ...
1
vote
0answers
20 views

What are the assumptions for applying Wald's equation with a stopping time

I am trying to understand the assumptions under which I am allowed to apply Wald's equation for a sum of a random number $N$ of random variables $X_n$, $1\leq n\leq N$. There seem to be several ...
1
vote
1answer
27 views

Expectation of constraint random walk

Problem description I am currently dealing with a practical problem that can be simplified to something like this: I start by setting a value to 0 Every minute, I try to increase or decrease 1 or ...
3
votes
0answers
34 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), ...
0
votes
3answers
76 views

Random walk on the real line

A particle stands on the origin of real line. In every second it jumps one unit to the left or right by the probability $\frac{1}{2}$. what is a probability that it reach to point $+1$?
2
votes
1answer
62 views

random walk on finite cyclic group

Suppose that I have a random walk on the finite cyclic group of order $d > 2$, where the initial probability distribution $Q$ assigns the values $p, q, r$ to $-1, 0, 1$, respectively, where $p + q ...
0
votes
1answer
35 views

Simple Random Walk and $n$th zero hitting time

I am reading an example in Durrett's book regarding the $n$th time the random walk hits 0. Consider a simple random walk, $X_i=1$ or $X_i = -1$ with equal probability. Let $S_n = X_1 + \dots + X_n$. ...
0
votes
0answers
14 views

Power law in power spectrum and memory.

If we generate white noise and do the FFT of it, we get the same amplitude for each of the frequencies. Therefore, the output of the FFT of the noise follows approximately the power law ...
1
vote
1answer
37 views

Random Walk on Clock Hands

We do a random walk on a clock. Each step the hour hand moves clockwise or counterclockwise each with probability 1/2 independently of previous steps. If you start at 1 what is the expected number ...
2
votes
1answer
72 views

How to analyse a random walk with random transition probabilities

Consider a $1$-dimensional random walk with discrete time steps. We start at the origin and at each integer position there is possibly different probability of moving right one step, or left one step. ...
1
vote
1answer
40 views

Simple Markov Chain: Random Walk on $\mathbb{Z}$

We are given a random walk on $\mathbb{Z}$, where $p_{i, i+1}= p < \frac{1}{2}$ and $p_{i,i-1}=1-p > \frac{1}{2}$, starting at $0$. Now we have to compute the probability that we eventually ...
1
vote
2answers
43 views

Simple Random Walk on Integers

Question concerning a simple random walk on 1D. Why the probability of hitting $\pm 2^n$ before return to $0$ is $2^{-n}$? I have no idea how to start... Thank's!
0
votes
0answers
21 views

Expected Value of Continuous Random Walk

I'm currently attempting my MMath master project. However, i'm a little stuck on an expected value of the continuous distribution. Its where i wish to change my random walk from a continuous walk to ...
1
vote
0answers
28 views

Random walk return for subgraph

Assume that $G$ is a finite graph and we have a simple random walk starting at some vertex $v$ of $G$. We fix $n$, and consider the probability that the random walk does not return to $v$ after $n$ ...
0
votes
0answers
7 views

Stochastic Process with mean reverting property

Here I am seeking for a definition of what kind of stochastic processes are called mean reverting stochastic process. That is, what are the properties that a stochastic process should obey in order to ...
0
votes
0answers
58 views

Calculate 1D random walk with alternating step size expected iterations to return to origin

I'm trying to solve a problem as outlined below; I'm a bit new, however, and I'm not sure how I could solve this problem. Assume someone has lost their keys, and uses an inefficient random walk to ...
0
votes
0answers
42 views

Random Walk, Markov Process

I'm stuck on a homework question and am wondering if anyone can offer some hints. Suppose we have some straight line graph G over the set $ V = \{1, 2, 3, ... , n\} $ of vertices, with an edge between ...
1
vote
0answers
27 views

Random walk on non-negative integers

Consider the Random walk on the non-negative integers with transition probabilities $$ p_{0,1}=1,~~~p_{i,i+1}=1-r,~~~p_{i,i-1}=r,~~~i\geq 1. $$ Determine $p_{00}^{(n)}$ As far as ...
0
votes
0answers
51 views

Recurrence of a trapped random walk

i am wondering how behaves a symmetric random walk on $\mathbb Z$ except in $\pm 1$ where it goes towards 0 with probability $p$ and towards $\pm 2$ with probability $ q < p \ (p+q=1)$ ? on which ...
2
votes
2answers
44 views

Expected time to get x units away when only able to move 1 unit either way

I know this is a common problem, but this problem has been bugging me after someone asked me it, and I can't find the answer anywhere on the Internet. Say we have a number line, and we start at the ...
0
votes
0answers
123 views

Random walk on infinite binary tree (recurrence, transience)

Consider a random walk on the infinite binary tree with root $x$ which has the following transition probabilities. $$ p_{x,0}=p_{x,1}=\frac{1}{2},~~~p_{y,y0}=p,~~~p_{y,y1}=q,~~\text{and ...
1
vote
0answers
34 views

Prove that $\text{Var} \tau = \frac{1 − (p − q)^2}{(p-q)^3} $ where $\tau$-stopping time

Let $S_n = \xi_1 + \dots + \xi_n$ be asimetric random walk such that $P(\xi_i = 1) = p > \frac{1}{2}$ and $P(\xi_i = -1) = q $. Let $\sigma^2 =1-(p-q)^2$ and let $X_n=(S_n-n-(p-q)n)^2 - \sigma^2n $ ...
2
votes
0answers
31 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 ...
0
votes
0answers
24 views

Theorem and proof about random walks

$\tau_{+d}=inf \{n: S_n =0, S_{n+1}>0, ... ,S_{n+d}>0 \}$ $\tau_{-d}=inf \{n: S_n =0, S_{n+1}<0, ... ,S_{n+d}<0 \}$ $q_n=P\{S_1>0,...,S_n>0\}=P\{S_1<0,...,S_n<0\}, n\in N$ I ...
3
votes
3answers
60 views

Guarantee to lose in +EV gamble?

I've checked it in numerical experiments but found it counter intuitive. A player start with $a_0>0$ dollars, let's denote the amount of money after $n$ rounds $a_n$ dollars. In each round, the ...
0
votes
0answers
30 views

Stochastic processes

Update I am a bit confused whether $y_t$ is independent over time under the following assumptions: Consider, first a RV $A$, that follows this process: $A_t = \rho A_{t-1} + e_t$, where $e_t$ is ...
1
vote
1answer
65 views

Standard deviation of absolute distance of a 1D random walk

Given a 1D random walk (simple +1, -1 movements from the axis) I've seen proofs that the expected absolute distance tends to Sqrt(2*n/PI) and I've plotted graphs of 1D random walks along with this ...
0
votes
1answer
30 views

Boundary conditions for random walk

Consider a simple asymmetric random walk $S_n$ which goes up with probability $p$ and down with $1-p$. For $b<x<a$ let $$r(x) = P( S_n\text{ hits }a \text{ before }b |S_0 = x). $$ This ...
1
vote
0answers
30 views

Limit of a random walk

Suppose we have a simple random walk: $X_n\pm1$ with equal probabilities. For any finite $n$, $E[\sum_{k=1}^nX_k]=0$. Does it imply that $E[\lim_{n\rightarrow \infty}\sum_{k=1}^nX_k]=0?$ Thank's! ...
0
votes
1answer
17 views

Simple random walk in the limit

Consider simple random walk: $X_n=\pm1$ with equal probabilities. $S_n =\sum_{i=1}^nX_i$. For finite $n$ we can write $$S_n=\sum_{i=1}^nX_i=\sum_{i=1}^nX_i^+ -\sum_{i=1}^nX_i^-$$ So that ...
1
vote
1answer
55 views

Expected number of returns to zero in a symmetric random walk - closed form

The expected number of returns of a symmetric random walk is given by $\sum_{k=0}^n \binom{2k}{k} / 2^{2k} -1$ The exercise is to compute an explicit form for this. I tried to do this in the ...
1
vote
2answers
31 views

Symmetric Random walk on $\mathbb {Z}^d$

Consider the symmetric random walk on $\mathbb{Z}^d $. Symmetric means that the probability of going into any of the $2^d$ directions is $1/2^d$. Starting in 0, what is the probability of ...