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

learn more… | top users | synonyms

1
vote
0answers
58 views

A matrix-multiplication random walk

Let $x \in \mathbb{R}^n$. Consider an $n\times n$ matrix $A$. Suppose we're interested in how $||A^nx||$ grows with $n$, the answer (excluding pathological cases) is that it scales exponentially with ...
2
votes
1answer
66 views

How to model a stochastic process, continuous in stepsize, which converges against a simple random walk?

I want to compute the probability distribution for a stochastic process with discrete number of steps, where each real value has a nonvanishing probability to be the next stepsize. And I want to ...
3
votes
1answer
334 views

Expected number of steps in a random walk with a boundary

Let's say I am trying to climb a flight of $N$ stairs. Each time I want to take a step, I flip a fair coin. Heads means I take a step up; tails means I take a step down. If I'm at the bottom of the ...
0
votes
0answers
26 views

Why must a stochastic process be at least second order in terms of differential equations?

A first order differential equation in $q(t)$ has a unique path through each possible value of $q(0)$. This is opposed to a stochastic process (e.g. random walk), where any place might be "hopped ...
0
votes
0answers
56 views

Identities in proving the arcsine law

In the course of proving the Arcsine Law for 1-dimensional random walk, there appear two combinatorial identities: (We are always considering a simple symmetric random walk of length $2n$) 1. ...
3
votes
0answers
42 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$ ...
0
votes
1answer
71 views

First-passage probability with absorbing boundary at origin (No Laplace)

I have the following problem which I would like to solve without using Laplace transform. Can you possibly help or provide pointers? What is the first-passage probability, and mean first-passage time ...
2
votes
0answers
136 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 ...
1
vote
2answers
35 views

Computing the sum of a Catalyn sequence— Random-walk motivated

How would one go about computing the following?: $$\sum_{n=0}^\infty (.5)^{2n+1} \cdot \frac{{2n}\choose{n}}{n+1}$$ The motivation is that this gives the probability that a random walk on a number ...
1
vote
1answer
39 views

Proving that the eigenvectors of this class of matrices are the binomial coefficients

So I'm trying to figure out the behavior of this system: you have $N$ coins, and every step, you choose one of the coins randomly and flip them. Now we imagine a bazillion of these systems. We call ...
1
vote
0answers
61 views

Markov Chain Problem

I have been stuck on this question for days and really need some help. There are two methods, A and B, to finish a work. Method A succeeds with probability 1/3, but if it fails one tries method B ...
3
votes
1answer
32 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
64 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 ...
2
votes
2answers
69 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
60 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
98 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
61 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
108 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 ...
6
votes
0answers
122 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
28 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
44 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
91 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
251 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
86 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
198 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 ...
0
votes
0answers
34 views

How to perform a stochastic search of the locality of a node in a network?

In a graph that may be a random graph (ER graph), scale free network, etc. I would like to obtain a distribution of the locality of the nodes surrounding a ...
1
vote
2answers
49 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
318 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
105 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
140 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
46 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
132 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
99 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
43 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
75 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
212 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$, ...
1
vote
1answer
179 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
92 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
78 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 ...
0
votes
0answers
55 views

Random walk with non-integer steps

Let $X_k\sim f(x)$ be a random variable taking values on $(-\infty, +a)$. The sum $S(n)=\sum_{k=0}^n X_k$ can be seen as a random walk with general distributed steps. Suppose $c_{neg}<0$ and ...
34
votes
1answer
982 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
89 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
96 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
74 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
135 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
143 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 ...