Skip to main content

Questions tagged [random-walk]

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

Filter by
Sorted by
Tagged with
3 votes
1 answer
37 views

Is the average of two identically distributed bounded martingales distributed in the same way?

I have seen this question and think it's sufficiently different (and well ranking on google) than the one I'm asking that makes it worth posting. Lets say you have a barrier reflecting martingale, of ...
ijustlovemath's user avatar
15 votes
4 answers
310 views

Optimal permutation of transition probabilities in random walk to minimize expected stopping time

Background Consider the set of integers $\{1,\dots,n+1\}$ and a set of probabilities $p_1,\dots, p_n \in(0,1)$. We now define a random walk/Markov chain on these states via the following transition ...
whpowell96's user avatar
  • 6,199
1 vote
1 answer
81 views

2D Modified Random Walk

A particle starts at the point (0,0). It can move +1 to the right with a probability $p$, it can move +1 up with a probability $q$, and it can move diagonally up and to the right with probability $r$. ...
Jbag1212's user avatar
  • 1,620
2 votes
1 answer
66 views

Autocorrelation of p-values after $n$ observations

For $i = 1, 2, \dots$, let $X_i \sim N(0, 1)$ and $Y_i \sim N(0, 1)$, with all observations independent of each other. Suppose that after observing $X_1, \dots, X_n, Y_1, \dots, Y_n$ we calculate the ...
Alex's user avatar
  • 2,391
4 votes
1 answer
54 views

Growth in sum-of-squares under random applications of $(a,b)\to (a+b/2,b-a/2)$ to $\{1\}^N$

A recent question considered the following problem: "Several (at least two) nonzero numbers are written on a board. One may erase any two numbers, say $a$ and $b$, and then write the numbers $a+\...
Semiclassical's user avatar
3 votes
1 answer
87 views

Distribution of the maximum of a "bridge" random walk

I found a card problem in an old book that essentially boiled down to this question: Suppose we have a random walk $S_n = X_1 + X_2 + \ldots + X_n$ that starts at $0$, where $X_i \hspace{0.1cm}$ is $1$...
Carlos Rosales's user avatar
0 votes
0 answers
13 views

Sufficient condition for matrix factorization as an undirected graph random walk matrix

Let $A$ be an $n\times n$ row-stochastic matrix. Is there a sufficient condition for $A$ to be factorized as $D^{-1} W$, where $W$ is a symmetric adjacency matrix for a weighted graph and $D=W\mathbf{...
phil's user avatar
  • 162
0 votes
0 answers
35 views

Biased random walk with chance of staying in place

A random walk has probability $x$ of moving $+1$, a probability $y$ of moving $0$, and a probability $z$ of moving $-1$. The PMF for arriving at position $m$ after $n$ steps can be found by summing ...
Jbag1212's user avatar
  • 1,620
-1 votes
0 answers
78 views

Random walk with indipendent but not identically distributed increments

Suppose $\{Z_i\}_{i=1,2, \ldots}$ are normally distributed (independent but not identically distributed) random variables with mean $\mu(y)>0$ and positive variance $\sigma^2(y)$. Therefore we ...
ag_c1768918's user avatar
0 votes
0 answers
29 views

Bounded random walk joint distribution

Let $(X_n)_{n\in\mathbb{N}}$ be a sequence of i.i.d. normally distributed random variable with zero mean and variance $\sigma^2$. Consider the bounded random walk $(S_n)_{n\in\mathbb{N}}$, defined ...
Aguazz's user avatar
  • 143
1 vote
1 answer
52 views

Mean hitting time of position-dependent random walk

The question I am interested in a continuous-time random walk on $K$ states, numbered $0$ to $(K - 1)$. For each $k$: I call $p_k$ the transition rate from state $k$ to state $(k + 1)$; I call $n_k$ ...
Matteo Monti's user avatar
1 vote
0 answers
47 views

Where will a Non-Symmetric Random Walk be after time=t?

I posted this question about ranking the final position of a symmetric random walk after $t$ steps in terms of likelihood: What is the 2nd most likely value of a Random Walk after time=t? I am now ...
konofoso's user avatar
  • 775
1 vote
1 answer
54 views

What is the 2nd most likely value of a Random Walk after time=t?

Here is a math problem I was thought of the other day involving Random Walks: Let $X_t$, $t \in \{0, 1, 2, ..., n\}$, be a (discrete time) stochastic process where $$X_t \in \{-1, +1\}$$ $$P(X_t = +1) ...
konofoso's user avatar
  • 775
8 votes
0 answers
182 views

probability of two confined randomly walking bodies overlapping

EDIT: I have tried to rephrase the problem, title, and context to my solution I am wondering about expanding a problem I have to the continuous domain. The problem is defined as such: Problem Given $N$...
gokudegrees's user avatar
1 vote
0 answers
20 views

Circular random walk to generate a Polygon

I am trying to generate a set of points distributed in such a way as to give a "rough circle" sort of shape. The points should not deviate too far from neighboring points, with larger jumps ...
Anthony Khodanian's user avatar
3 votes
0 answers
52 views

Convergence of quotient of sample variance and sample mean

Let $(X_k)$ be a collection of i.i.d random variables with finite fourth moment satisfying $\mathbb{E} X = 0$ and $\mathbb{E} X^2 = 1$. What can be said about the convergence of the following quotient ...
Kayle of the Creeks's user avatar
5 votes
1 answer
117 views

Expected travel length of a symmetric random walk on the n-dimensional unit cube from one corner to the opposite corner

Let $E:=\{0,1\}^n$ be the corners of a n-dimensional unit cube. Let $(X_n)_n$ be the symmetric Random Walk on E. A jump from i to j, $i,j\in E$ has probability 1/n if $|i-j|=1$. I am interested in the ...
Peter Strouvelle's user avatar
3 votes
0 answers
83 views

Advection-Diffusion Equation from biased random walk

Many PDE textbooks (e.g. Logan's Applied PDEs) derive the 1D diffusion equation from a random walk on the line. As an exercise, it asked to show that the advection-diffusion equation could be derived ...
Ron Shvartsman's user avatar
1 vote
0 answers
52 views

Expected stopping time for biased random walk with increasing stepsize

Let $S_n$ be a stochastic process, with $$ S_{n+1} = S_n - 1 + \begin{cases} n^2 & \mathrm{with\;probability\;}\frac{1}{2}\\ -n^2 &\mathrm{else} \end{cases}. $$ Let now $T:=\inf\{n\geq0:S_n\...
lorenzw's user avatar
  • 73
2 votes
2 answers
99 views

Random walk on the edges of a square where staying at same position is allowed

The classic question of finding the expected number of steps to move from one corner of a square to the opposite. I found an intuitive way to do it by considering that we are at position $(0,0)$ and ...
Axo's user avatar
  • 301
1 vote
0 answers
77 views

Conditional probability of a random walk

Let $X$ be a random loss and $P$ a premium for a insurance company to transfer this risk. Let us assume that the insurance company chooses a premium equal to the expected loss, so $P=\mathbb{E}(X)$. ...
Frodo361's user avatar
  • 319
0 votes
2 answers
62 views

Calculating the Expected Hitting Time on an undirected graph.

I have the following undirected graph: where $K_{n-1}$ is a complete graph with $n-1$ nodes and $v$ is connected to a node $u \in K_{n-1}$. I am trying to set up a formula to calculate the exact ...
user1171376's user avatar
2 votes
0 answers
33 views

Brownian motion runs through a circle

Let $(B_t)$ be standard Brownian motion starting from 0, and $\mathbb{R} \to \mathbb{R}/2\pi\mathbb{Z} = S^1$ be a canonical projection. I want to calculate the expectation of the stopping time $T$, ...
nessy's user avatar
  • 582
0 votes
0 answers
23 views

Bounding d-regular graph traversal length for every starting node and every traversal

Question: (Past exam question i'm using to revise) Let $G = (V,E)$. A connected d-regular graph. Let $v_1 \in V$. Assume that at each node, the ends of the edges incident with the node are labelled $1,...
Willow's user avatar
  • 1
0 votes
2 answers
38 views

Solving Difference Equation from Feller's

I'm trying to derive the closed solution for $a_n : 0<n<m$, $$a_n = 1 + \frac{a_{n+1}} 2 + \frac{a_{n-1}}2,\ \ \ \ a_0= a_m = 0$$ Basically, it's the hitting time for a simple random walk. A ...
zzz's user avatar
  • 35
0 votes
1 answer
12 views

Probability of SSRW being nonnegative, conditioning on returning to zero at a certain time

Question: suppose $\{X_n\}$ is a simple symmetric random walk on $\mathbb{Z}$, compute $$P(\min_{0\leq m\leq 2n}X_m = 0 | X_{2n}=0)$$ My only idea was that by the symmetric nature of the process, ...
喵喵露's user avatar
  • 193
1 vote
0 answers
34 views

Prove: every strongly connected graph has at most one stationary distribution without manipulating with eigenvector

In mcs.pdf, Problem 21.12 says: A digraph is strongly connected iff there is a directed path between every pair of distinct vertices. In this problem we consider a finite random walk graph that is ...
An5Drama's user avatar
  • 416
1 vote
1 answer
40 views

Prove the gambler can expect to play forever in the gambler’s ruin scenario

In mcs.pdf, Problem 21.2 says: In a gambler’s ruin scenario, the gambler makes independent $1$ bets, where the probability of winning a bet is p and of losing is $q ::= 1-p$. The gambler keeps ...
An5Drama's user avatar
  • 416
4 votes
1 answer
155 views

circular random walk - markovian frog

Suppose there are $n$ lily pads on a unite circle. A frog is sitting on one of them at time $t=0$. Every minute, this frog makes a jump to a neighboring lily pad with a probability $p=1/2$. Find the ...
user147813's user avatar
1 vote
0 answers
37 views

Exercise 3.1 of Algebraic Combinatorics by Richard Stanley

Exercise 3.1: Let $G$ be a (finite) graph with vertices $v_1, \ldots, v_p$. Assume that some power of the probability matrix $M(G)$ defined by $(3.1)$ has positive entries. (It's not hard to see that ...
Jonathan McDonald's user avatar
4 votes
1 answer
48 views

Combinatorial proof that $\sum_{k=1}^{n} k {2n \choose n+k}=\frac{1}{2}n{2n \choose n}$ [duplicate]

I'd like to find a combinatorial/algebraic proof of the identity: $$\sum_{k=1}^{n}k{2n \choose n+k}=\frac{1}{2}n{2n \choose n}$$ The only proof of this that I've been able to find on the Internet, ...
N. S.'s user avatar
  • 81
0 votes
1 answer
50 views

Hitting time and first hitting time

The following statement is in fact a middle step that I want to prove when I try to show that the probability of the first hitting time of symmetric random walk in $\mathbb{R}^{n+1}$ equals $t$ is ...
PPP's user avatar
  • 447
0 votes
0 answers
18 views

Are expected numbers of visits to a point for a random walk in $\mathbb Z^d$ explicitly known?

Let $\lbrace Z_n\rbrace$ be the standard random walk in $\mathbb Z^d$ starting at $0$ (i.e. $Z_0=0$ a.s.). Is there an explicit formula to compute the expected amount of visits to a certain point $(x,...
confusedTurtle's user avatar
1 vote
1 answer
60 views

Random walk probability that walk gets to a before b

I'm having difficulty applying electrical network concepts to solve this exercise. My current approach is setting up a voltage generator from node $p$ to $q$ with $v(p)=1$ and $v(q)=0$, and assigning ...
Broder_Salsa's user avatar
0 votes
0 answers
34 views

Simulated random walk for forecasting

I have made an exercise where I simulate the outcomes for the change in the exchange rate. The simulated outcomes are supposed to mimic a random walk and are generated with the mean and variance ...
Johanna W's user avatar
1 vote
0 answers
35 views

Random walk metropolis within Gibbs

I tried to implement the Random Walk Metropolis within Gibbs algorithm from Marie Therese Wolfram's article on Inverse Optimal Transport, but I feel like there's an error. In the algorithm, they ...
user600785's user avatar
4 votes
0 answers
54 views

Has this random process been studied on grid graphs?

As an offshoot of a different discussion I got curious about (uniform) random spanning trees on grid graphs (torus graphs in particular, to avoid having to think about edge effects) and what their ...
Steven Stadnicki's user avatar
0 votes
1 answer
29 views

Analyzing Expected Profit in a Symmetric Random Walk with Trading Actions

Problem Formalization: I am examining a problem where a stock price $X_t$ follows a symmetric random walk starting at 10, and increments or decrements by 1 unit at each step with equal likelihood. The ...
XiaoBanni's user avatar
1 vote
0 answers
55 views

Is it possible to know the information of edges of the graph from its adjacency matrix's eigen vectors?

Suppose $G$ be a connected simple graph, and $A(G)$ be its adjacency matrix such that $a_{ij}=\begin{cases} 1 ,i \sim j & (ij \in E(G))\\ 0 ,i \not\sim j & (ij \not\in E(G)) \end{...
user avatar
2 votes
1 answer
52 views

Why do three random walkers on $\mathbb Z$ meet infinitely often?

A paper of Dvoretzky and Erdős refers to the fact that three random walkers independently undertaking a simple symmetric random walk on $\mathbb Z$ will meet infinitely often with probability $1$, but ...
RDL's user avatar
  • 582
0 votes
0 answers
74 views

Solve for probability of 0 successes where number of attempts is a random variable with unknown distribution

I am interested in solving the following problem: Imagine we have some event A that can occur with probability p, let q = 1 - p. The number of attempts we have for event A to occur is itself a random ...
noamb's user avatar
  • 11
0 votes
3 answers
101 views

Transience of random walk on the natural numbers.

Let $X = (X_n)_{n\in\mathbb{N}} \sim \text{MC}(\lambda,P)$ be a Markov chain on the natural numbers such that $\forall i\neq 0,\, (p_{i,i+1}=2/3$ and $p_{i,i-1}=1/3)$ and $p_{0,1}=1$ (every other ...
Choripán Con Pebre's user avatar
0 votes
0 answers
36 views

Bounded Random Walks vs Non-Bounded Random Walks

Recently I posted this question here on the probability distribution of two Random Walks (1 dimensional and on the integer line) meeting each other: When and Where will 2 Random Walks Meet for the ...
stats_noob's user avatar
  • 3,196
2 votes
1 answer
110 views

Gambler's ruin with asymmetric probabilities

A gambler with a capital of $1$ dollar goes to a casino, where they participate in a series of games. In each game, regardless of the others, they can win $1$ dollar with probability $p$ or lose $1$ ...
thefool's user avatar
  • 1,118
1 vote
1 answer
101 views

What Percent of the Time will a Given Random Walk will Behave a Certain Way?

Suppose I have a 1 Dimensional Random Walk (on the integer line) with the following properties (initial conditions): At time=0 it starts at position=0 At each time point, there is a 0.5 probability ...
stats_noob's user avatar
  • 3,196
6 votes
0 answers
106 views

When and Where will 2 Random Walks Meet for the First Time?

This is a question I thought of recently: (Based on some set of initial conditions, i.e. initial positions and movement probabilities , and the current time and positions) When and Where will 2 Random ...
stats_noob's user avatar
  • 3,196
2 votes
0 answers
26 views

Proof of Theorem 5.38 in Morters and Peres' Brownian Motions book

In the proof of Theorem 5.38 which states that if $\tau_{a}$ is the hitting time of $a>0$ and if $\sigma_{a}=\inf\{t\geq 0:B(t)\geq |a|\}$, then $\int_{0}^{\tau_{a}}\mathbf{1}_{\{0\leq B(t)\leq a\}}...
Dovahkiin's user avatar
  • 1,285
0 votes
0 answers
66 views

Probability that two paths don't intersect

This question is inspired by this other question but it could be simpler. I think also that by using an answer here and the inclusion-exclusion principle we can get a solution for the linked question. ...
Fabius Wiesner's user avatar
1 vote
2 answers
145 views

Simple solution to random walk

The final score of a football match was 4:3 in favour of the home team. How many ways could the result have gone if there was a period of the match when the away team was leading? I have learnt of a ...
user555076's user avatar
2 votes
1 answer
86 views

Why does the Wiener process use $\sqrt{dt}$ instead of $dt$? Why does simulation of random walk in continuous-time not occur as expected?

I'm trying to make a point about Markov processes and ran into difficulty understanding how to simulate continuous-time random walks. A discrete-state discrete-time random walk has the equation: $x_{n+...
Coletti's user avatar
  • 33

1
2 3 4 5
50