5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Do I understand correctly that your bug is simply performing a simple random walk on the lattice $Z^r$? I do not quite see the equivalence of the questions (why do you need all digits to appear in order to return to the origin). Can you clarify? $\endgroup$ – ofer zeitouni Dec 15 '13 at 7:19
  • $\begingroup$ @ofer When you say $Z^r$, do you mean $\mathbb{Z}^r$? If you do, then no. At every point, the bug has exactly $r+1$ choices of direction, which are the vertices of a regular simplex (link) at which the bug is centered. The simplices must also all be oriented in the same direction. Also, in the second question, the digits don't have to appear in order; there simply has to be a point such that the number of occurences of the digit $n$ is equal for all $0\le n\le b$. Does that make sense? $\endgroup$ – Dylan Pizzo Dec 15 '13 at 10:49
  • $\begingroup$ I'm still having troubles following what you mean. Can you describe it for r=2? $\endgroup$ – ofer zeitouni Dec 15 '13 at 11:48
  • $\begingroup$ @oferzeitouni Actually, Ben Barber's answer below contains an illustration of the r=2 case. $\endgroup$ – Dylan Pizzo Dec 15 '13 at 12:57
4
$\begingroup$

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}$.

$\endgroup$
  • $\begingroup$ Just trying to clarify: When you say unit vectors of length r+1 with exactly one entry nonzero, you mean an r+1 dimensional vector with all components 0 except for one which is 1? Also, I apologize if this is a stupid question, but what is $S_n(j)$? $\endgroup$ – Dylan Pizzo Dec 16 '13 at 13:13
  • $\begingroup$ @Dpiz: When you say unit vectors of length r+1 with exactly one entry nonzero, you mean an r+1 dimensional vector with all components 0 except for one which is 1? Yes. What is $S_n(j)$? The $j$th component of $S_n$. $\endgroup$ – ofer zeitouni Dec 16 '13 at 16:59
  • $\begingroup$ Does that mean that $A_n$ should be with $j$ ranging from 0 to r if the vectors have r+1 components? (same for $j'$ as well except going from 0 to $j$)? Also, just trying to clarify, you say that $S_n$ is binomial(n,1/(r+1)); by that I assume you mean $\binom{n}{\frac{1}{r+1}}$? $\endgroup$ – Dylan Pizzo Dec 17 '13 at 13:16
  • $\begingroup$ 1) range is 1...r (i.e. I do not look at r+1 component, which is determined by the others. You can take 1,..., (r+1), it's the same event). 2) No; I mean Binomial RANDOM VARIABLE (n, 1/(r+1)); this means, with n attempts and probability of success equal 1/(r+1). $\endgroup$ – ofer zeitouni Dec 17 '13 at 14:04
3
$\begingroup$

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.

enter image description here

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.

$\endgroup$
  • $\begingroup$ I actually want to know if it reaches the origin in particular, not just the main diagonal. I don't really know the term recurrent, but after looking it up on wikipedia, it sounds like it means it has 0 probability of going off to infinity, is that correct? By the way, thanks for the picture, that is perfectly accurate. $\endgroup$ – Dylan Pizzo Dec 15 '13 at 13:08
  • 2
    $\begingroup$ Representations of points in the $\mathbb Z^{r+1}$ picture are only unique up to multiples of $\sum_{i=0}^r v_i$, so hitting the main diagonal corresponds to returning to the origin. (Compare to your sequences in which each value appears equally often.) Yes, recurrent means exactly that you will return to where you started infinitely often with probability 1. $\endgroup$ – Ben Barber Dec 15 '13 at 13:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.