Random walk by simplex vertices

Question

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 distinct 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=2$ as calculated by Mathematica.

EDIT:

I'm starting to doubt my expression above as the answer.

Answer 1

Thanks to Ben Barber's answer, one can represent your question as follows.

Let $u_i$ be an i.i.d. sequence of unit vectors of length $r+1$ with exactly one entry nonzero, and set $S_n=\sum_{i=1}^n u_i$. Return to the origin at time $n$ corresponds to the event $A_n=\{S_n(j)=n/(r+1), j=1,\ldots,r\}$. Once one hits the main diagonal, the process restarts, so a transience/recurrence criterion is whether $\sum_n P(A_n)<\infty$.

Now, because $S_n(1)$ is binomial(n,1/(r+1)), for $n$ an integer multiple of $r+1$, $$P(S_n(1)=n/(r+1))\sim c_1/\sqrt{n}$$ and, for $j=2,\ldots,r$, $$P(S_n(j)= n/(r+1)|S_n(j')=n/(r+1), j'=1,\ldots,j-1)\sim c_j/\sqrt{n}.$$ Therefore, $$P(A_n)\sim c/n^{r/2}$$ which implies recurrence for $r=2$ and transience for $r\geq 3$.

The probability in the OP is thus $1$ for $r=2$. As to the probability for $r>2$, an exact computation seems out of reach, but the asymptotics as $r\to\infty$ is dominated by the first cycle returning to $0$, i.e. by $\prod_{j=2}^{r}(1-j/(r+1))\sim c e^{-r}$.

Answer 2

This is less an answer than a collection of observations that have grown too long for a comment.

First, an illustration of the definition in 2D as I understand it.

Next, an elaboration of your comment on the equivalent form of the problem. Write $v_0, \ldots, v_{r}$ for the vertices of the reference simplex centred at $0$. Then every point that can be visited by the random walk has representations $\sum_{i=0}^r \lambda_iv_i$, where the $\lambda_i$ are non-negative integers, and these representations are unique up to adding multiples of $\sum_{i=0}^rv_i$. From this point of view the random walk is on $\mathbb Z^{r+1}$ with all steps taken "up and to the right", and you want to know whether you hit the main diagonal. This is discussed for $r=1$ in this previous MO question.

Finally, a piece of philosophy. If you instead ask only the weaker question of whether your random walk is recurrent, I expect that you will get the same answer as for $\mathbb Z^r$, as the large scale behaviour should not depend sensitively on the exact structure of the underlying lattice.