Skip to main content
2 of 6
changed simplex to regular simplex.
Dylan Pizzo
  • 395
  • 2
  • 11

Random walk by simplex vertices

I apologize if this question is well-known, but I was unable to find it mentioned anywhere.

There exists a bug which moves around in $r$-space. The bug begins at the origin of this $r$-space. If the bug is at the center of a regular $r$-simplex (all of which are oriented the exact same direction) with radial length of $1$, then the bug moves to one vertex of the simplex chosen at random with equal probabilities for each vertex. Call each instance of the bug moving, a step.

My question is: What is the probability, as a function of $r$, that there exists a number $n>0$ such that just after the $n$th step, the bug is at the origin?

An equivalent question is:

Given an infinite sequence of digits, with any given digit in the sequence being randomly chosen with equal probabilities inclusively between $0$ and $b$, what is the probability, as a function of $b+1$, that there exists a point in the sequence such that there are an equal number of occurrences of all $b$ digits out of the digits up to that point?

Some work I have done has provided me with a solution that is not in closed form:

$$-\sum_{k\in A}\left(\prod_{i=1}^{k_{length}}\frac{-(r k_i)!}{(r^{k_i} (k_i!))^r}\right)$$

where $A$ is the set of all finite sequences of integers and $k_{length}$ is the length of the sequence $k$.

Unfortunately, I cannot remember how I obtained this result; if I recreate it, I will edit this question. I also have a lower bound of $0.7$ for $r=3$ as calculated by Mathematica.

Dylan Pizzo
  • 395
  • 2
  • 11