# Tagged Questions

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

48 views

### Why is this true with random walks?

Let $S_n=\sum_n{X_n}$ a random walk with $P[X=1]=p=1-P[X=-1]$. Prove that for any $k \in Z$ $P[\cup_{n \geq1} \{S_n\geq k\}]= (P[\cup_{n \geq1} \{S_n\geq 1\}])^k$ I do not understand why is this ...
51 views

### Help with a symmetric random walk problems

Given a simple symmetric random walk $X_1,X_2,…,X_n,…$ where $X_t,t=1,2,…$ are i.i.d random variables distributed according to $\Bbb P(X_t=1)=1/2$ and $\Bbb P(X_t=-1)=1/2$. Define partial sum ...
32 views

### An inequality for standard random walk.

How to prove that $\Bbb P_1(\lim\sup_{n\to\infty}\frac{\log \bf{x}(n)}{\log n}\le \frac{1}{2})=1$, with the suggestion that $\bf{x}(n)$ goes to $\infty$ like $\sqrt{n}$. Here $\bf{x}_n$ is the ...
80 views

### Random walk in a graph

This is a question about random walk from vertex $s$ in a graph (can be directed), which is defined in the following manner: The random variable $X_0$ (whose possible values is the set of vertices) ...
77 views

### Wald's Identity for non-i.i.d. Case

I am looking for Wald's Identity for non-i.i.d. case as discussed in the following links: https://en.wikipedia.org/wiki/Wald%27s_equation What are the assumptions for applying Wald's equation ...
47 views

### Random Walk UpperBound

enter image description hereIs it possible to prove that for any symmetric Random Walk the absolute value of its partial sum $S_n$ never exceeds $\sqrt{2 \pi n}+\sqrt{\pi / 2}$ ? I run some ...
21 views

### Transience of random walks starting from each of the sites which have been already visited

Consider a simple random walk on $\mathbb{Z}^d$, $d \geq 3$, which starts from the origin. As $d \geq 3$, there is a positive probability that the random walk never visits the origin again. Now, let ...
17 views

33 views

### Continuation of random walks

I have trouble understanding the following identity: $\mathbb{E}[e^{i\theta\cdot T_t}]=\sum_{j\geq 0}{e^{-t}\frac{t^j}{j!}\mathbb{E}[e^{i\theta\cdot S_j}]}$. I see that somehow it uses the following ...
29 views

### What's the difference between a white noise process, IID process and random walk?

Just need some clarification between these concepts. Is an IID with mean zero white noise process? Also is random walk a summation of white noise process?
135 views

### What is the relationship between eigenvector and computing PageRank?

I read several papers about PageRank and didn't get stuck in understanding the idea of PageRank because it is simple, but I got stuck in computing PageRank, those papers talk about some mathematical ...
38 views

28 views

### Infinite expected number of visits with Green function

The random walk Green function is defined by $G(x,1) = \sum_{n\in \mathbb{N}_0} P(S_n = x)$, with $x\in\mathbb{Z}^d$. $G(x,1)$ equals the expected number of visits to $x$. Now I want to prove that ...
96 views

### Showing stopping is finite almost surely

Consider a discrete random walk taking values +1 or -1 with probabilities p and q, respectively. Let $S_n = \sum_{k=1}^{n}X_k$. Let $[-A,B]$ be an interval, $A,B \geq 1$. Now define \tau =\min(n:n ...
31 views

### Clarification on Two-player Gambler's Ruin variant.

I looked around and found many questions related to two-player variants of Gambler's Ruin but could not find what I had in mind. I needed clarification on a certain step while deriving the expression. ...
42 views

### Hitting probabilities for random walk with +m/-n steps

Random walk theory in the real axis: a frog starts at k initially, and in each move, it moves either by distance m to the right (from i to i+m) or by n to the left(from i to i-n), where k,m,n are ...
85 views

### Expected distance of a random walk of distance $k$ on the $k$th step

I am trying to sharpen my intuition on some random-walk style results. Suppose we are looking at a random walk on $\mathbb{Z}$ starting at $0$. At the $k$th step, we either walk to the left $k$ ...
47 views

### 2-dimensional random walk experiment

Question: Consider a board covered by square tiles(like a chess set only of a size of your choosing) and colored like a chess set. Two "people" are placed in different areas of the board and ...
64 views

### Step in computation of the expected cover time for the simple random walk on a discrete circle

I'm having a little trouble understanding part of an example in Lawler's Intro to Stochastic Processes ("Simple Random Walk on a Circle" example on page 32). The problem is the following: Suppose ...
51 views

### Can a Random Walk algorithm be considered a computational intelligence algorithm?

I am implementing different computational intelligence algorithms from the local search area. These are Hill Climbing and Simulated annealing. Also I am implementing another algorithm with a mere ...
126 views

### Probability Generating Function of a Stopping Time, Random Walk

Let $\{S_k\}_{k\geq0}$, $S_0=0$ be a symmetric simple random walk. For an integer $n\geq1$, let $\tau_n=min\{k\geq1:S_k\notin(-n,n)\}$ be the first time k such that $S_k$ leaves the region $(-n,n)$, ...
41 views

### Limit of Covariance and Correlation of Random Walk

Let $S_n=X_1+...+X_n$, $n\geq1$ be a random walk, where $EX_k=\mu$ and $Var(X_k)=\sigma^2$, $0<\sigma^2<\infty$. a)Find the covariance $Cov(S_n,S_m)$ and the correlation coefficient ...
234 views

### Last vertex visited by the symmetric random walk on a discrete circle

$n$ cats form a circle, indexed from $0$ to $n-1$. At first, there is a ball at the cat $0$. We throw a coin with the probability of $p$ heads up. If the coin is heads up, we pass the ball clockwise, ...
29 views

### Random walks with limited number of visits

I'm interested in random walks (esp. their hitting times) such that the number of visits to each state is limited by some parameter $K$. Is there any canonical name for such stochastic processes? ...
78 views

### Random walks intuition [closed]

I came across the reflection principle and this explanation at Is there an intuitive way to see this property of random walks? However, I can't understand the reasoning in the answer about mirroring ...
17 views

### Formula for the analytical computation of Eigenvalues for random walks of order one and two on regular lattices

I have a question with respect to random walk penalties in statistics. In Bayesian statistics an adequate prior for modeling a $n$-dimensional random vector $\boldsymbol{x}$ as a random walk of order ...
26 views

### Calculating the Variance of a Pure Random Walk

I am trying to calculate the first two moments of the random walk below: $y_t$=$y_0$+$\sum_{j=1} ^t u_j$ Mean: E[$y_t$]=$y_0$ Variance: E[$y_t ^2$]=t$\sigma^2$ I understand how to obtain the 1st ...
38 views

### When is a lazy random walk matrix positive definite?

There are a number of nice results about when the graph Laplacian is positive definite and positive semi definite. However, I can't seem to find any analagous results for random walk matrices, and was ...
I learn stochastic process by myself and currently, doing an exercise about random walk. Suppose a random walk $\eta(t,s)$, (1) $\eta(0,s) = 0$; (2) $\eta(t,s)$ is defined on a set of sample point ...
Lets say I have a random variable $X(t)$ which describes some unit of motion of a living organism and $X(t)$ is itself a timeseries since this unit of motion changes in time. I would like to be able ...