0
votes
4answers
85 views

Random walk on a finite square grid: probability of given position after 15 or 3600 moves

An ant is walking on the squares of a 5x5 grid - it starts in the center square. Each second, it will choose (with equal probability) to do one of the following: Move north one square Move south ...
2
votes
1answer
58 views

Lattice Path Spaces.

It is well known that the number of paths from $(0,0)$ to $(n,k)$ in $\mathbb{N^2}$ with the set of steps $\{(1,0),(0,1)\}$ is ${n+k \choose k}$. This is the minimum number of steps needed to get to ...
0
votes
0answers
55 views

Stationary distribution for random walks on directed graph

There is an equation (Eq. (2)) in reference by Lovasz and Winkler about the stationary distribution of a random walk on directed graphs that I would like to find references for where the equation is ...
0
votes
0answers
42 views

Random looking Gray Codes or Hamiltonian Cycles on Hypercubes

Cyclic Gray codes come in many flavors and correspond 1-1 to Hamiltonian cycles on hypercubes. I would like to find a type that looks like a random walk on the hypercube. In a sense this is an ...
2
votes
0answers
49 views

A random walk on the unit distance graph in $\mathbb{R}^n$

Define a graph $G_n$ whose vertices are the points in $\mathbb{R}^n$ with an edge connecting any two points that are one unit apart. Such a graph is called the unit distance graph in $\mathbb{R}^n$. ...
0
votes
2answers
94 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 ...
5
votes
2answers
113 views

How can we directly see that the number of random walks starting and ending at the origin is ${n\choose n/2}^2$?

In an infinite two-dimensional square-shaped grid, we define four directions, north, south, east, west. We thus have $4^n$ random walks of length $n$. If we end where we started, for every north step ...
1
vote
2answers
203 views

Calculating expected value of random walk with one stop value.

I know that for a random walk with two stop values, the expected value of the number of steps needed is $ab$ where the stop values are $-a$ and $b$ and the initial position is at 0. What about for ...
2
votes
1answer
80 views

What is the probability that the robot steps on the bomb?

Suppose a robot is initially placed at $0$ on the number line, and is programmed to take steps of integer length in the positive direction between $1$ and $k$, inclusive, where $k$ is a positive ...
1
vote
1answer
82 views

Number non self avoiding closed walks surrounding some point

While studying some Peierls-like arguments in statistical physics I thought about the following problem: We have some 2d-integer lattice like this, for simplicity infinite in all directions. Now fix ...
1
vote
0answers
56 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 ...
12
votes
3answers
275 views

Select a new value from last $N$ values; how long until the last $N$ are all the same?

Say first we have N distinct numbers in a line, like 1,2,3,...,N, in each round, we choose a ...
6
votes
2answers
554 views

A question on calculating probabilities for the random walk

I am currently working on a high school project revolving around the 'Cliff Hanger Problem' taken from ”Fifty Challenging Problems in Probability with Solutions” by Frederick Mosteller. The problem ...
0
votes
2answers
172 views

Question from section 1.5 of Chung's Spectral Graph Theory

I'm (slowly) reading Fan Chung's Spectral Graph Theory. At the moment, I'm in section 1.5 which is about eigenvalues and random walks. There's a small technical point that puzzles me. The context ...
2
votes
1answer
97 views

$1$D bidirectional random walk question

In a $1$D random walk on x axis a particle can turn left with probability $\frac{3}{4}$ and right with probability $\frac{1}{4}$. What is the probability that $|x|\leq 1 $ for $1\leq ...