8

We are creating a circular hub consisting of charged 0 and 1 particles next to each other, beginning with four of them: 0, 1, -0 and -1 in this order. Every 1 sec we randomly select one of each kind and add it next to the last one. Whenever a 0 particle finds itself next to a -0 or a 1 particle next to a -1, they both vanish. Assuming it is equally likely to select each of the 4 kinds, what is the probability that at some point the hub vanishes completely?

I assume it is not as easy as

$\frac {1}{4}.\frac {1}{3}.\frac {1}{2}$, right?

I can't figure out of anything else...

Any help?

Sal.Cognato
  • 1,527
  • Your probability does not take into consideration cases where the hub vanishes after adding some particles without vanishing at first, like for example $0,1,-0,-1,0,0,0,-0,-0,-0,1,0,-1,-0$ – Sil Jul 22 '18 at 12:37
  • @Sil yes but how do we take into account ALL these cases to calculate the total probability? – Sal.Cognato Jul 22 '18 at 12:43
  • I don't quite understand how the fact that the hub is circular enters into this. You have $0$, $1$, $-0$, $-1$ to start with, so I assume the $-1$ is next to the $0$. Now you add a new particle. Am I right in thinking that you add it between the $-1$ and the $0$, and it will vanish (together with its partner) if it's either a $1$ or a $-0$? And then you keep adding new particles between the end and the beginning of the sequence, and they can vanish either with the end or with the beginning of the sequence? – joriki Jul 23 '18 at 04:45

2 Answers2

6

As it was pointed out in the comments, the solution below is for the case when the particles are arranged in a line, rather than circularly. So please modify the proof below.

To simplyfy the definition of the process, in each step we have the following possibilities. Either with probability $1/4$ the length decreases by 1, or with probability $3/4$, the length increases by 1. So this is an unbalanced Drunkard walk (one of the most basic Markov chains there is) on infinitely many states indexed by the non-negative integers. Your initial state is $4$, and the only absorbing state is 0. Your question is the probability of absorption.

This can be computed using standard theory in Markov chains.

Let $p$ be the probability that from a given state $n\geq 1$ you at some point reach $n-1$. Note that this $p$ is independent from $n$. So from the law of total probability (based on the case distinction that the first move is to the left or to the right) we have

$$p= \frac{1}{4}\cdot 1 + \frac{3}{4}\cdot p^2$$

Proof: if the first move is to the left, then we are done (i.e., the probability is 1 in this case). If the first move is to the right, then we have to reach $n-1$ from $n+1$. This is equivalent to reaching $n$ from $n+1$ and then reaching $n-1$ from $n$, hence the probability is $p^2$.

So $3p^2-4p +1 = 0$, or equivalently, $(3p-1)(p-1)=0$. Thus $p=1$ or $p=1/3$. It is easy to see that $p$ is not $1$, so $p=1/3$.

(There is another argument: consider the finite state Drunkard walk with the same transition probabilities starting from state $1$. Then there is a well-known closed formula for the probability of absorption, which tends to $1/3$ as the number of states tends to infinity.)

So we can move one step to the left with probability $1/3$. Thus, to ever reach the state that is four steps to the left from the initial state, has probability $(1/3)^4=1/81$.

A. Pongrácz
  • 7,418
  • 1
    This is a good answer for the linear case. But the question asked is for a circular arrangement. – Teoc Jul 22 '18 at 15:12
  • You are right, I missed that in the problem description. Anyway, it is easy to modify the argument. Only the numbers are different, the technique is the same. – A. Pongrácz Jul 22 '18 at 16:09
  • No, the technique I believe is completely different, since the identity of each element at the ends matter for the probabilities. – Teoc Jul 22 '18 at 16:20
  • I am not sure about "completely", but you are right again. One needs to be more careful. – A. Pongrácz Jul 22 '18 at 16:25
  • If the probability didn't turn out to be $1$ (see my answer), e.g. if we had four different types of pairs, then I don't think this method could be directly applied to the circular case to calculate the probability, because in the circular case additional pairs can be annihilated, and the probability for that to happen depends in a potentially complicated way on the history. – joriki Jul 23 '18 at 06:12
  • I think this is a wrong answer. If you keep adding particles at the end, the probability for going from n \to n-q would not be it. Imagine a probability tree and add the paths leading to the n-1 position. – Michael Paris Jul 23 '18 at 06:54
  • @MichaelParis: I don't understand that. What do you mean by "would not be it"? The answers seems correct to me for the case of a linear sequence. Where exactly do you see an error? – joriki Jul 23 '18 at 10:12
2

I understand the procedure as follows:

We have a sequence of particles that starts out as $0$, $1$, $-0$, $-1$. We keep adding particles to the end of this sequence. The sequence is circular in the sense that the last particle is considered to be adjacent to the first particle, so they can potentially vanish together if they match. Even if particles from either end of the sequence vanish, new particles are always added to the end of the sequence.

Then the probability that all particles will eventually vanish is $1$. In each step, we have probability $\frac12$ of at least one pair of particles vanishing (since the ends of the sequence are of two different types and we uniformly randomly choose one of four types). More than one pair of particles might vanish in a single step if the new ends also match, but we can ignore that since a probability of $\frac12$ for a single match per step is already enough. The number of particles in the sequence is a biased random walk with probability $\frac12$ of taking a step $-2$ and probability $\frac12$ of taking a step $+1$. A biased random walk almost surely diverges towards the side of the bias, so the sequence almost surely vanishes completely. This would even be true if there were an additional pair, $2$ and $-2$, since we'd then take a step $-2$ with probability $\frac13$ and a step $+1$ with probability $\frac23$, so the expected value of the step would be $0$ and the random walk would still almost surely reach any given point.

joriki
  • 238,052