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
20 views

Reading material on Random Walk on S_n using Transpositions

I am from an engineering background and I wanted to get hold of some very basic reading material on Random Walk on $S_n$ (symmetric group on n letters) using Transpositions. Could someone suggest ...
0
votes
0answers
25 views

Probability distribution for a random walk in arbitrary dimension

I'm trying to find the probability distribution for a random walk on a lattice with lattice constant a in arbitrary dimension d. The rules for my walk is that in each step the walker has to move to an ...
0
votes
0answers
22 views

How to get more profit in stochastic process?

Suppose there is a system, for each step, I cost something but I didn't know how much I cost, and the system return to me something, which follow Guassian distribution and the expectation is what I ...
2
votes
0answers
31 views

An inequality for symmetric random walk

I need to show that if $(X_j)$ are symmetric i.i.d. random variables with partial sums $S_n:= \sum_{j=1}^n X_j$, then for all $x \geq 0$ $$P(|S_n| > x) \geq \frac{1}{2} P(\max_{1 \leq j \leq n} ...
0
votes
0answers
27 views

Final step of a random walk proof

I am working through the last bit of a random walk proof to show that a 3-d random walk is transient. The result I am looking for states that: $\frac {1}{2}^{2s} {{2s}\choose{s}} \sum_{j+k\leq{n}} ...
1
vote
0answers
28 views

Expected time of reaching 0 of a simple symmetric random walk

Consider the symmetric, simple random walk on $S = \{0, 1, \ldots , k\}$ for $k \in \mathbb N$. Let $$T = \min \{ n \in \mathbb N_0|X_n = 0\}$$ be the first time where the process reaches $0$ and ...
-1
votes
0answers
22 views

Simple Symmetric Random Walk [closed]

Use Hint: Show first that for any random variable N with range {0,1,...},
-1
votes
0answers
25 views

Eigenvalues of transition matrix of a random walk on a line

Consider the following $n\times n$ stochastic matrix describing a simple random walk on a line: $$ P=\begin{bmatrix}\frac{1}{2} & \frac{1}{2} & 0 & \cdots & 0\\ \frac{1}{3} & ...
2
votes
0answers
44 views

2d random walk on the nonnegative quadrant using martingale techniques

I know the basics of (discrete time) martingales, and I'd appreciate any help and suggestions on how to prove the following using martingale techniques. Let $Z_n$, $n\ge 0$ be a random walk on the ...
0
votes
1answer
69 views

Probability that random walkers meet

I was wondering about a question about Random Walks. I came across various papers where the probability of 2 random walkers in 1 dimension and 2 dimension starting at the same point and returning to ...
2
votes
1answer
55 views

Random walks : Hitting and recurrence Times relation

I have trouble understanding that how $$E\left[T_0|X_{0} = 0\right] = 1 + E[H_0|X_0=1] $$ where $T_0 = \inf\{n \geq 1:X_n = 0 \}$ and $H_A =\inf\{ n\geq 0: X_n \in A \}$. In other words $T_0$ is the ...
0
votes
1answer
25 views

How to calculate the correlation coefficient of two independent random walks to demonstrate spurious regression?

I heard of non-stationary time series could result in spurious regression, so I want to know, as sample size goes to infinity, how to calculate the correlation coefficient of two descrete independent ...
0
votes
0answers
24 views

A random walk with an exit

Let's consider a random walk. We start on the tile $n_0$. For our $q$th step, if we're already on the tile $k$ then we have a probability $P_{q,k,p}$ to go to the tile $p$ with $p\in\mathbb{N}$. ...
1
vote
1answer
47 views

Show expectation is finite of an asymmetric walk

Where does this result come from? $$\mathbb{E}\left[\left(\frac{q}{p}\right)^{S_n}\right]\leq \left(\frac{q}{p}\right)^n + \left(\frac{q}{p}\right)^{-n}$$ where $$S_n = \sum_{i=1}^{n}X_i$$ and $0\leq ...
0
votes
1answer
26 views

Series of random numbers on a continuous function

At one point, I read about a function used to generate random numbers that follow a continuous pattern. By this I mean random numbers that as a series is random, but in which items tend to be ...
0
votes
0answers
29 views

Expected number of returns by time n in a symmetric 1-d random walk?

How do we prove that $E(N_{2n})=(2n+1){{2n}\choose{n}}(\frac{1}{2})^{2n}-1$ I started working on it. And I see that $E(N_{2n})=\Sigma_0^n{{2k}\choose{k}}(\frac{1}{2})^{2k}-1$ Therefore the problem ...
1
vote
0answers
29 views

capacity of biased random walk in $\mathbb{Z}^2$

Let $P_{x,y}$ the probability that a random walk starting from $x$ will ever visit $y$. Consider a biased random walk in $\mathbb{Z}^2$. Let $A_k$ be the set of vertices having a distance less than ...
2
votes
1answer
54 views

Random walk : probability of reaching value $i$ without passing by negative value $j$

This is just some question that popped out of nowhere while starting studying random walks, and I don't really know how to approach this. Say I have a random walk that starts at zero, and goes up or ...
0
votes
0answers
20 views

Optimal stopping strategy

I try to solve the following problem : Given a series of random variables : X1,X2,... such that each one can get either -1 or 1 with probability 0.5, give a strategy to maximize the expected value of ...
1
vote
1answer
36 views

Independence of random variables derived from a Random walk

Let $w=(w_x)_{x \in \mathbb Z}$ be i.i.d random variables taking values in $(0,1)$. Let $(X_n)_{n \in \mathbb{N}_0} (\mathbb{N} \cup {0})$ be a Markov chain (more specifically a simple random walk ...
0
votes
0answers
20 views

1-D random walk weighted towards the origin

I would like to model a random walk in one dimension where the walker is attached to the origin by a rubber band, such that the walker's probability of moving toward origin increases with the distance ...
5
votes
0answers
45 views

Probability on entering direction of a simple random walk

Let $X(n)$ be a simple random walk on $\Bbb{Z}^2$. Also we define $S_{R} = \inf\{n > 0 : X(n) \notin [-R, R]^2 \} $ : the exit time of the square $[-R, R]^2$, $T_{v} = \inf\{n > 0 : X(n) = ...
0
votes
1answer
46 views

Why the probability of a sequence is simply the multiplication?

In studying the random walk in one dimension I had a doubt on basic probability. The point is the following: we consider a random walk with $N$ steps consiting of $n_1$ steps to the right and $n_2$ ...
9
votes
0answers
112 views

Expected range of simple random walk in $\mathbb{Z^2}$

Let $(Y_k)_{k\geq0}$ be a simple random walk process. The range of an $n$-step random walk, $R_n$, is a random variable that characterizes the number of distinct points visited at time $n$: ...
0
votes
0answers
38 views

The characteristic function for the random walk

I want to determine the characteristic function of the probability distribution of a random walk. The probability distribution of a random walk is: ...
1
vote
1answer
78 views

Expectation and Variance of random walks

Consider random walks of fixed length (e.g. $5$) starting at node $u$ in an undirected and connected graph with $N$ vertices. If a node $k$ has $N_k$ edges, the probability of the walk reaching any of ...
0
votes
1answer
16 views

$\sqrt{n}$ in scaled random walk

In a reference, it is stated that $W^{(n)}(t)=\frac {1}{\sqrt{n}}M_{nt}$ with : $W^{(n)}(t)$ as scaled random walk and $M_{nt}=\sum_{j=1}^{nt}X_j$. Where does $\sqrt{n}$ come from? Would you ...
0
votes
1answer
29 views

Probability - Random Walk Type Problem

Suppose two teams play a series of games, each producing a winner and a loser, until one time has won two more games than the other. Let G be the number of games played until this happens. Assuming ...
0
votes
0answers
30 views

diffusion- stuck

In a round room of radius R, a large number of coins N of diameter d are randomly dispersed upon the floor. A ladybird starts from the centre of the room, crawling at speed v. Suppose that every time ...
0
votes
0answers
31 views

Random Walks - $n$ particles on a $n-clique$

We take $n$ particles and put them on $v$, a vertex in $n$-size Clique $G$, where each vertex has a loop to itself. Each particle does a Random Walk on the clique and the $n$ Random Walks are ...
4
votes
1answer
43 views

Random walk with finite expected stopping time

Let's say each $X_i$ is a simple random variable taking on values 1 or -1 with probability $1/2$ each. Then $S_n = \sum_{i=1}^{n} X_i$ is a random walk. Set $T = \min \{n\in\mathbb{N} \, : \, S_n = ...
0
votes
0answers
8 views

compare hitting time of two random walks with reset action

Let $s^i_k = s^i_{k-1} + x^i_k$ with $s^i_0 = 0$ for $i=1,2$. Additional constraint on $s^i_k$ is that $s^i_k$ cannot be negative, i.e., $s^i_k$ is reset to be zero whenever it becomes negative. The ...
1
vote
0answers
16 views

a problem on random walk and maximu of its summation

Suppose $X_n$ is random walk with $P(X_n=1)=1-P(X_n=-1)=p=1-q$. $M_n=\max_{1\le i\le n} S_i$, $Y_n=M_n-S_n, T_a=\min\{S_n=a\}$. Find $P(\max_{0\le k\le T_a} Y_k <y).$
2
votes
1answer
39 views

$E(S_T^2)\not=E (\sum_{i=1}^T \sigma_i^2) $ when $E|T|<\infty$

I am currently learning random walk and come across a problem concerning stopping time. The question asks to give an example that $X_1,X_2,...$ independent r.v. with mean $0$ and variance ...
1
vote
1answer
27 views

Why random walk sample path seen as if it is continuous-time stochastic process?

Random walk is a discrete-time stochastic process. In many references, instead of using dots to draw its sample path, why does random walk use line-styled graph as if it is a continuous-time ...
3
votes
2answers
42 views

Random walk on a tree

Consider a Cayley tree with coordination number 3 (http://en.wikipedia.org/wiki/Bethe_lattice). Consider two sites, $x$ and $y$, having a distance $k$ one from another. What is the probability that ...
1
vote
0answers
40 views

Maximum of *Absolute Value* of a Random Walk

Suppose that $S_{n}$ is a simple random walk started from $S_{0}=0$. Denote $M_{n}^{*}$ to be the maximum absolute value of the walk in the first $n$ steps, i.e., $M_{n}^{*}=\max_{k\leq ...
0
votes
1answer
15 views

Let $S_n$ be a Simple Random Walk. What is $E[S_m|S_n]$ if $m < n$?

Let $S_n = W_1 + ... + W_n$ be a simple random walk with $W_i$ IID and $P[W_i = 1] = P[W_i = -1] = 1/2$. Find $E[S_m | S_n]$ when (a) $m > n$ and (b) $m < n$. For part (a), I get the answer of ...
0
votes
4answers
46 views

Expected number of steps

I play a game as follows. A bucket contains four red balls and three green balls. At each step, a ball is chosen at random from the bucket, with each of the balls there being equally likely to be ...
2
votes
2answers
96 views

Bounding profits of gambler by Azuma Inequality

A gambler plays the following game: In each round, he can pay any $0 < p < 1$ dollars, and win 1 dollar with probability p (independently). Show that the probability that the gambler's net ...
0
votes
1answer
133 views

Random Surfer as a Markov Chain

Consider a random surfer who begins at a web page (a node of the web graph) and executes a random walk on the Web as follows. At each time step, the surfer proceeds from his current page A to a ...
0
votes
1answer
96 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 ...
1
vote
0answers
28 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
31 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
1answer
101 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 ($n$ is the sink state) ...
0
votes
1answer
36 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
61 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 ...
4
votes
1answer
81 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
109 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
87 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 ...