For questions on random walks, a mathematical formalization of a path that consists of a succession of random steps.
1
vote
0answers
10 views
Dimension free Concentration bounds for Martingales
Consider the following random process which is defined on $n$ numbers $0\leq x_1,\ldots,x_n\leq 1$:
At each step, pick an arbitrary number, say $x_i$. Then randomly (and independently) change its ...
2
votes
1answer
41 views
An application of Donsker's theorem.
Let ${X_i}$ be iid with $E[X]=0$ and $Var(X)=\sigma^2$ Let $S_0=0$ and $S_n=X_1+...+X_n$ for all $n \ge 1$. Show that $\lim_{n\rightarrow \infty}P(S_k>0 \space for \space k=n,n+1,\dots,2n)=1/4 $.
...
1
vote
1answer
27 views
Random walk serial correlation
Given a model $$Y_t =b_0 + b_1 \cdot X_t + b_2 \cdot Z_t + e_t,$$ where the error term $e_t$ follows a random walk form of serial correlation $e_t = e_{t-1} + u_t$. Further assume $u_t$ has zero mean ...
2
votes
1answer
55 views
Proof: Mean and Variance of the squared distance of a random walk in n-dimensional space
consider a $x$ step random walk starting from origin in $n$-dimensional space where each step is taken into a random direction and has a distance of 1, i.e., each step is a vector on the ...
0
votes
0answers
37 views
Random Walk, Coin flip game [closed]
Consider the coin flipping game, where player $A$ pays $B$ \$1 for each Heads, and vice versa for each Tails. (The coin is unbiased here.) Let $X_1$ be the random variable recording the first time ...
1
vote
1answer
75 views
A Boundary crossing result for discrete brownian bridge
Let $S_n$ be a random walk with gaussian increments with $S_0=0$, i.e. $S_n-S_{n-1}\sim N(0,1), n\geq 1$. Fix $a>0,b\in \mathbb{R}$ and $c<a+bn$. Define the new process
$$
...
1
vote
1answer
36 views
Help calculating variance of a random variable
This is related to this question Average end point of 1-dimensional random walk?
Given several discrete random variables such that $p(Z_i=1-2k)=p$, where $k$ is a small real number, and ...
2
votes
1answer
38 views
Mean displacement for a random walk on a $d$-dimensional lattice
How does the mean displacement of a random walk on a $d$-dimensional integer lattice (or $d$-dimensional hexagonal lattice) scale with the number of steps $N$ in the walk? Is the displacement always ...
0
votes
1answer
27 views
Average end point of 1-dimensional random walk?
Is it possible to estimate the average end point of a 1-dimensional random walk of n steps where the probability of going "left" is p and going "right" is 1-p?
Thanks.
0
votes
1answer
62 views
Random walk with absorbing barriers
Consider a random walk with absorbing barriers at $0$ and $3$. $\mathbb P(S_{n+1}-S_n=1)=0.6$ and $\mathbb P(S_{n+1}-S_n=-1)=0.4$. What is the probability of eventual absorption at $0$, given that the ...
4
votes
2answers
78 views
Prove that a random walk on $\mathbb{Z}_+\cup \{0\}$ is transient
Prove that a random walk on $\mathbb{Z}_+ \cup \{0\}$ is transient with $p_{i,i+1}=\frac{i^2+2i+1}{2i^2+2i+1}$ and $p_{i,i-1}=\frac{i^2}{2i^2+2i+1}$.
So since this Markov chain has only a single ...
1
vote
0answers
36 views
Extracting hitting times from the pseudoinverse of a Laplacian matrix for an undirected graph
Provided a pseudoinverted Laplacian matrix for an undirected graph $G$, how can I extract first passage and commute times between vertex pairs in $G$?
1
vote
1answer
31 views
Cover Time for Random Walk on a cycle
I'm trying to find the expected time to cover all $N$ nodes on an undirected cycle graph, starting from a given node $k$. The probabilities of moving clockwise and anticlockwise are $\frac{1}{2}$ ...
0
votes
0answers
27 views
planar walks and catalan numbers
prove that following numbers are equal:
(unordered) pairs of lattice paths with n+1 steps each, starting at (0,0), using steps (0,1) or (1,0), ending at the same point and only intersecting at the ...
3
votes
1answer
68 views
Random Walk on Z
Let $S_n$ be the symmetric random walk on $\mathbb{Z}$. How do i calculate
$P(\limsup_{n\rightarrow\infty} S_n=\infty)$?
I already know that the probability is 1 but I don't really know how to start? ...
0
votes
1answer
53 views
Simple Probability Matrix
Consider a simple model that predicts whether you pass you next test or not based on the result of your previous test.
If you pass your previous test, then you have 0.2 chance you will pass your ...
2
votes
0answers
66 views
Teleporting random walk
Given a directed graph $G = (V,E)$, to define a random walk on $G$ with a transition probability matrix $P$ such that it has a unique stationary distribution (as mentioned in this paper)
I used a one ...
0
votes
1answer
64 views
The variance of a simple random walk/process
I've been trying to wrap my head around this for the past day. Please help!
Let $\epsilon_i = \pm 1$ with equal probabilities independently for $i=1,...,N$.
Then $Z_i = \epsilon_1 + ... + \epsilon_i$ ...
0
votes
1answer
105 views
The random walk $S_n=a+\sum_{i=1}^nX_i$
Consider a variant of random walk defined as
$$S_n=a+\sum_{i=1}^nX_i,$$
where $X_i$ takes either value $2$ with prob= $p$ or value $-1$ with prob =$1-p$. What is $P(S_n=b)$?
0
votes
0answers
96 views
Random walk, Cat and mouse
Here is the problem.
In graph G, on different vertices there is cat and mouse. Cat and mouse do independent
random walk, but time is synchronous, in one unit of time both cat and mouse do one step.
...
2
votes
0answers
104 views
Random walks in $1$, $2$ and $3$ dimensions [closed]
I know that this may seem easy but I have no clue where to start (if possible could you answer this in the simplest way possible)?
Consider a person who is at the position $x=0$ on the $x$-axis at ...
1
vote
1answer
44 views
Inequality between two Random Walks
Let's consider two Random Walks,
$$x^{(1)}_t = x_0 + \sum_{i=1}^{t}\xi^{(1)}_i,$$
$$x^{(2)}_t = x_0 + \sum_{i=1}^{t}\xi^{(2)}_i.$$
The random variables $\xi^{(1)}_i$ are i. i. d. They take values on ...
3
votes
1answer
115 views
A Coupled Random Walk on the xy-Plane
Consider a point on the $xy$-plane whose position is updated in iterations. In each iteration, the point undergoes, with equal probability, either an $A$- or a $B$-update, defined as follows:
...
3
votes
1answer
91 views
successive doubling the stake until head appears
I consider the following gaming system: Start with 1 dollar and always bet on head (coin tossing). You always double your stake until the first head appears. Maximum rounds: $n$
I formulated it as a ...
1
vote
1answer
38 views
Asymmetric random walk with unequal step size other than 1.
Say, an asymmetric random walk, at each step it goes left by 1 step with chance $p$, and goes right by $a$ steps with chance $1-p$. (where $a$ is positive constant).
The chain stops whenever it ...
0
votes
1answer
75 views
Expected hitting time of one of two barriers
In the webpage "hitting time of one of two barriers", the probability that a non symmetric random walk hits one of two barriers is computed. The walker starts from $x=0$ and the barriers are located ...
0
votes
1answer
35 views
Probability related to random walks in two dimensions
I'm trying to show that two random walks will eventually meet in a two dimensional setting but I can't figure out where to start. Can someone lead me towards the right direction?
4
votes
1answer
166 views
Random walk on lollipop graph
Hi i am trying to prove expected Hitting time on the Lollipop graph. It is a graph on $n$ vertices with clique on $n/2$ vertices and path joined to this. Let vertex $i$ be a vertex on the clique, ...
2
votes
1answer
123 views
How to solve recurrence in two variables
How can you solve this simple looking recurrence relation in two variables?
$f(a,b) = 1 + \frac{a f(a+1,b+1) + (x-a)f(a+1,b)}{x}$
The function $f$ is defined for non-negative integer values $a$ and ...
0
votes
2answers
117 views
hitting time of one of two barriers
Let's consider a one-dimensional Random Walk. At each time the walker moves of one step to the right with probability $p$ and to the left with probability $q$, with $p+q=1$. The walk is not symmetric, ...
1
vote
1answer
64 views
Random Walk probability game
I try to solve some exercises from olympiads and I have difficulties with this one:
Consider a round table with 20 people. One of these players receive a book and chooses one of his neighbors and ...
4
votes
0answers
96 views
probability of this event happening
Play $(n+1)t$ rounds of the same coin-tossing game and the coin is fair ($n$ is a fixed natural number). Please help me find the following probability:
$P$(the number of rounds of tossing that ...
2
votes
1answer
77 views
is the possibility of this event happening positive?
Play 2*t rounds of the same coin-tossing game, please express P(t rounds show head and the other t rounds show tail, and at any time point between 0 and 2t, the number of coin landing head is no less ...
1
vote
0answers
109 views
Extinction probability of a simple birth death process
X is a simple birth death process with birth rate $\lambda n$ and death rate $\mu n$
Embedded within a simple birth death process is a simple random walk.
Let $Y_n $ be the value of X at the time of ...
4
votes
1answer
99 views
Chance of being able to quit while ahead in a betting game (Markov chain with gambler's ruin)
Suppose a player starts with $N$ chips, and is playing a game with odds $O$, betting 1 chip in each iteration. When the player reaches 0 chips the betting must end.
What is the probability that at ...
1
vote
1answer
116 views
Simple random walk hitting time asymptotic behavior
Let $p(n,t)$ be the probability that a simple random walk starting at state $n$ hits $0$ within $t$ steps.
How big can $p(n,t(n))$ get for large $n$ when $t(n) = o(n^2)$? It seems like maybe it could ...
0
votes
0answers
69 views
Random Walk Metric in 2D and 3d
I have a set of N random walk. Each random walk as the same lenght and the same
(-1 1) cardinality. It's just the (-1 1) distribution along the walk that varies.
I would like to know if there is a ...
-1
votes
1answer
106 views
Stationary distribution for different types of graph
This is a follow-up questions to posts:
Stationary distribution for directed graph
Stationary distribution for different types of graph
The definition of stationary distribution in ...
0
votes
1answer
166 views
Stationary distribution for directed graph
I want to implement the algorithm of graph partitioning of sparse directed graph.
In this algorithm after computing the transition matrix ,we should compute the stationary distribution of the random ...
0
votes
2answers
111 views
Random Walk Proof Problem
I have to do the following problem:
Let $(s_n)_{n\geq 0 }$ be a 1-dimensional, unbiased random walk. For $a,b\in\mathbb Z$, let $T_a=\inf\{n>0:s_n=a\}$ and $T_{a,b}=\inf\{n>0:s_n=a\hspace{3mm} ...
2
votes
1answer
90 views
Existence of a stationary distribution for a random walk
Consider a random walk on a infinitely countable connected graph.
We assume that each vertex has finitely many neighbors and that we have a uniform bound of the number of neighbors at each vertex.
The ...
3
votes
0answers
79 views
Two gamblers' ruin
I'm trying to work out the solution to a variant of the gambler's ruin. Here's my version:
There are two very unlucky but friendly gamblers A and B who decide
to pool their money together to form a ...
0
votes
1answer
66 views
transience and recurrence of a random walk
I have a random walk $\{X_n\}$ where each transition causes moving one step to the right (with probability $p$) and one step to the left (with probability $1-p$). Now $X_n \to \infty$ as $n\to\infty$ ...
1
vote
1answer
108 views
Expected number of steps till a random walk hits a or -b.
On wikipedia I read that the expected number of steps till a 1D simple random walk hits either $a$ or $-b$ is equal to $ab$. (I have seen this result also on other websites.)
However, no proof or ...
1
vote
2answers
178 views
Stopping Time, Random Walk
I'm trying to solve this problem and don't know where to start. If someone could prove it or tell me how or point me to any relevant information I'd very much appreciate it.
Let $(s_n)_{n\geq0}$ be a ...
0
votes
0answers
118 views
Expected number of steps for reaching K in a random walk
Assuming steps are +1/-1 with a 50/50 probability. What is the expected step count for reaching 10, 100 or K?
2
votes
2answers
73 views
A problem on left skip free random walk with downward drift
Let $X_i$, $i \geq 1$ be i.i.d random variables. Let $P_j=P(X_i = j)$ and suppose that $$\sum_{j=-1}^{\infty} P_j=1$$. That is the possible values of the $X_i$ are $-1,0,1,\dots$. If we take $$S_0=0, ...
0
votes
0answers
26 views
Optimal way to move in a grid to find a random walker
Consider an $n$ times $n$ grid. Assume there are two agents $A$ and $B$.
At time $t_0$, agent $A$ is at square $(n,n)$ and $B$ is at random square. At time $t+1$, agent $B$ has moved one square ...
3
votes
1answer
38 views
Random mixing of the space of triangulations of a surface
Summary: How quickly does the edge-flip random walk in the space of triangulations of a closed, connected, orientable surface converge to the uniform distribution over all triangulations?
Let $M$ be ...
1
vote
1answer
116 views
Finding the exact solution of a difference equation
We know a particle moves two units to the right with probability $p$, or $1$ unit to the left with probability $q$, hence $(p+q=1)$.
$$q_k=P\left(S_n=0\mid S_0=k\right)$$
We are asked to find the ...
