3
votes
1answer
54 views

2D random walk variation

If a point on a 2D lattice is allowed to take a random walk by taking a unit step either up, down, left or right, there is probability $1$ of reaching any point (including the starting point) as the ...
1
vote
1answer
28 views

Random walk on free group on two elements

Let $F_2$ be the free group on two elements, generated by $\{a, b\}$. We perform a random walk on $F_2$, starting at the identity element $e$ and uniformly at random selecting one of ...
1
vote
1answer
59 views

Proving a property of hitting times of a simple random walk on $\mathbb{Z}$

I'm reading the course notes of a probability course about martingales currently and I'm trying to solve some of the exercises, however I'm very much stuck with the following exercise: Let $\left\{ ...
2
votes
1answer
54 views

Random walk around circle

For one of the exercises of my homework I need to answer the following question, but I am not sure how I should apply gamblers ruin theory to solve this problem (it is stated as a hint, not that I ...
5
votes
1answer
94 views

Probability of random walk returning to 0

Given a symmetric 1-dimensional random walk starting at 0 -- what is the probability of the walk returning $k$ times to 0 after $2N$ steps? I know that the total number of paths it can take is ...
3
votes
1answer
26 views

Randomly moving about a lattice, probability that I return to my original location?

I thought of this question when I was walking aimlessly around my neighborhood. Here's my question: My house is on an infinite lattice of points: say my house is at $(0,0)$. I start walking north (it ...
4
votes
0answers
58 views

Uniform integrability of the maximum of a random walk with negative drift

Given $S_k^{(n)} = X_1^{(n)} + ... + X_k^{(n)}$ for all $k,n\in\mathbb{N}$, where the $X_i^{(n)}$'s are iid with mean $-\gamma$ for some $\gamma > 0$ and unit variance. Let ...
0
votes
0answers
28 views

Estimation of random walk maximum and minimum positions

I am trying to prove that, if a simple and symmetric random walk $S$ starts at $S_0 = 0$ and finishes at $S_n = N$ with $N > 0$, then if there is a maximum $M > N$ and a minimum $B < 0$ (both ...
2
votes
2answers
68 views

Random walk on tree

You begin at a root node that has 2 children. Each of those two children have two more children, and each of those children have two final children (i.e., there are 15 nodes in the graph). How do I ...
1
vote
1answer
46 views

{Probability}: choosing keys from a pool without replacement

The OP is trying to understand the following question. The OP understand that if you can always write out the term $$P(X=k) \implies (1-\frac{1}{N})(1-\frac{1}{N-1})\cdots(1-\frac{1}{N-k+1}),$$ ...
0
votes
1answer
59 views

Expected number of steps and probability

I have a problem that I am not quite sure how to solve using my elementary knowledge of probability. My question is this: suppose a friend and I are playing a game. We both start at 0 points, and ...
0
votes
1answer
56 views

Probability: deviation from the mean

I am having trouble to understand the following. If $S_n=X_1+X_2+......+X_n$, where X_1,X_2 are Bernouli (p). I don't understand this. So you get an intermediate point Constant* sqrt(n). To the ...
3
votes
0answers
42 views

Standard deviation of a quantum walk?

The standard deviation of a classical random walk with $n$ steps is $\sqrt n$ - Standard deviation of a random walk. I have read in many places that the standard deviation of a quantum walk $n$ with a ...
3
votes
1answer
78 views

Function of a uniformly distributed continuous random variable

Basically, I'd like to add $n$ random vectors in a 2 dimensional space of unit length and of angle $\theta$ relative to a global axis. The probability density function of the angle $\theta$ is a ...
3
votes
3answers
440 views

Probability a random walk is back at the origin

I have a symmetric random walk that starts at the origin. With probability $1/6$ it goes right by one and with probability $1/6$ it goes left by one. With probability $4/6$ it stays put. After $n$ ...
0
votes
0answers
40 views

Expected number of steps in a random graph walk

Suppose I have a directed graph $D(V, A)$ where the edges have weights on them. Let's notate the weight function $w: A \rightarrow [0, 1]$. If $f, t \in V$ and $a \in A$ such that $a = (f, t)$ then ...
1
vote
1answer
38 views

Reaching a level before another for a random walk

Suppose we are given a simple random walk starting in $0$, i.e. $(X_k)_{k\in\mathbb{N}}$ with $P[X_k=+1]=P[X_k=-1]=\frac{1}{2}$. What is the probability of hitting the level $a$ before hitting the ...
0
votes
1answer
50 views

Probability of random walk traversal

Consider a random walk on an connected, non-bipartite, undirected graph G. Show that, in the long run, the walk will traverse each edge with equal probability. Note: The walk can traverse each edge ...
0
votes
0answers
33 views

Random walk on an infinite resistive lattice

I have been referring to a paper http://arxiv.org/abs/physics/0405135 to determine the effective resistance using random walks for an infinite square resistive lattice Though the author seems to ...
2
votes
2answers
47 views

Generate random sample with three-state Markov chain

I have a Markov chain with the transition matrix $$\pmatrix{0 & 0.7 & 0.3 \\ 0.8 & 0 & 0.2 \\ 0.6 & 0.4 & 0}$$ and I would like to generate a random sequence between the three ...
2
votes
2answers
86 views

Urn Problem - black and white balls, infinite trials.

Imagine that there are 10 black balls and 20 white balls in an urn. Two balls are removed at random from the urn. The second ball removed is recolored, such that it matches the color of the first ...
1
vote
2answers
150 views

Distribution of the first passage time of a Gaussian random walk

Does anyone know the distribution for the first passage time of a Gaussian random walk i.e. $$ S_n = \sum_{i=1}^n X_i $$ where $X_i$ are iid normally distributed random variables. The first passage ...
3
votes
1answer
63 views

Random walk where increment depend on current position

Consider the following stochastic process, $$b(i+1) = b(i) + \xi_i (b_i),$$ where $\xi_i(b_i) \in \{-1, k \}$ are the independent increments having the following distribution: $$\begin{align} P (\xi ...
0
votes
1answer
60 views

2 dimensional random walk - hit of targets

Consider a random walk in $\mathbb{Z}^2$, $x(j) = x(j-1) + \xi_j$, where the increments are random variables independent and identically distributed with finite support, the expectation $m := ...
0
votes
0answers
43 views

Conditional expectation of random walking

Let $Y_1,Y_2,...$ be independent random variable such that $VarY_i = \sigma^2$ and $EY_i = \mu_i$. Let $$S_{n+1} = \sum_{j=1}^{n} Y_j$$ Find $E(S_{n+1}| S_n,...,S_1)$. My attempt: We have: ...
4
votes
1answer
93 views

Drunk problem involving probability of being in a circle.

This is the typical drunk problem wherein the person is confined to moving either to the North, South, East, or West but never diagonally with just one step. A step has a length $L$. What is the ...
1
vote
1answer
183 views

First step analysis on random walk

Let us consider random walk on integers {0,1,...,N} where $P(N,N)=1$,$P(0,1)=1$, $P(N,N-1)=0$ and all other connections have probability $\frac{1}{2}$. Using first step analysis, compute $p_{00}$ for ...
4
votes
1answer
77 views

random walk in a certain environment

Consider the following random walk in one dimension, starting from $r(0)=0$. $$ r(i+1) = r(i) + \xi, $$ where $\xi(i, r(i))$ is an increment with distribution $P(\xi=1) = \frac{c^{r(i)}}{i-r(i)+1}$ ...
1
vote
1answer
48 views

ruin of the gambler with probability to die

Consider a random walk on $\mathbb{Z}$ starting from $i >0$. With probability $p$ it moves to the nearest neighbor on the left, with the same probability it moves to the nearest neighbor on the ...
0
votes
0answers
44 views

Absorption probability in 1D RW with asymmetric step sizes, $ x<0 $

What is the probability of absorption at $ 0 $, as a function of position $ x $, for a 1D random walk (on $ \mathbb{Z} $) with asymmetric step sizes? For example, suppose that you can take two steps ...
0
votes
1answer
132 views

Probability for asymmetric random walk

How to express this in equation form(in terms of position(x) and time(N)), like the one for symmetric random walk, $\displaystyle P(x,N) = \frac{N!}{(\frac{N+x}{2})! ...
0
votes
1answer
63 views

random walk with dependent increment

Consider the following sort of random walk. The position of the walker at time $t$ is represented by the random variable $r(t)$, with $r(0) = 0$. The variable satisfies the following equation, $$ ...
0
votes
1answer
73 views

Random walk with weighted probabilities

Taking a walk on $\mathbb{N}$, starting at 1, I need to find out how many steps I expect to take before returning to the origin, as a fraction. For each step, I either walk forward, backward, or stay ...
0
votes
2answers
72 views

How Do You Calculate Probabilities of Random Events Occuring in Sequence?

So I have a series: $f(x_{n+1})=x_n \pm t$ and $f(x_0)=W$ What I'd like to calculate is the probability in terms of $t$ and $W$ (assuming they're any constant $W>t$) that any $f(x_q)=0$ for all ...
3
votes
3answers
115 views

Random walk problem in the plane

Let a particle in the plane $R^2$ executes random jumps at discrete times $t= 1, 2, ...$. At each step, the particle jumps from the point it is a distance of lenght one. The angle of any new jump ...
2
votes
0answers
47 views

mean displacement inequality for random walk with drift away from zero

Suppose $X_n$ is a nearest neighbor random walk on the integers with transition probabilities biased towards moving away from zero but with the bias asymptotically vanishing as you move away from ...
4
votes
2answers
112 views

The problem of the drunkard in a valley.

We consider a Markov chain on a subset of positive integers $S =$ {$0, 1, 2, 3, .......N$}, with transition probabilities defined as follows: The chain jumps only one unit to the left or right. ...
0
votes
1answer
103 views

Reflected Simple Random Walk

Suppose $W = (W_{n})_{n\geq0}$ is a symmetric random walk on $\mathbb{Z}$ with $SRW(\frac{1}{2})$. Define $\hat{W_{n}} = (\hat{W}_{n})_{n\geq0}$ by $\hat{W_{n}} := |W_{n}|$. Show that for $y \gt 0$: ...
1
vote
2answers
79 views

1-d random walk probability bound calculation problem

I'm recently reading the paper about digital fountain code "LT Codes" by M. Luby. There is a statement seems simple with the author "The probability a random walk of length $k$ deviates form its mean ...
1
vote
1answer
205 views

Meaning of root mean square distance in random walk

This is a question about a simple random walk problem where we want to measure the average distance from the start in various experiments of N steps each. If d is distance moved during one such ...
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 ...
3
votes
1answer
336 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
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. ...
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 ...
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. ...