4
$\begingroup$

Let $\mathcal{T}$ be the infinite countable $3$-regular tree graph. Pick a vertex in this graph, call it the root. Let the root carry the value $0$.

Next, assign $1$ to the neighbours of the root. Then, assign $0$ to the vertices at distance $2$ from the root. And so on, changing values layerwise.

Now, equip each vertex with a Poisson clock ($\lambda=1$), all clocks are independent. At each time the clock of a vertex ticks, the vertex updates its value to be the value of most of its neighbours.

What is the probability that the root changes value infinitely often?

Thank you.

(See a closely related question: Graph with Poisson Clock at each Vertex)

$\mathbf{EDIT:}$ A possible direction for a solution: Define a positive valued function $f$ on the vertices (or on the edges?), such that the sum of $f$'s values at all vertices is finite. Now, each time a vertex pops and changes value, $f$ is nullified there. If ticks at neighboring vertices cause that vertex to become unstable - not to carry the value of most of its neighbours - $f$'s original value at that vertex returns. If the sum of all $f$'s values at time $t$ is called $S_t$, then convergence at all vertices occurs iff $\lim_{t\to \infty}S_t$ exists.

Mind you, $S_t$ is a bounded stochastic process, and therefore has a bounded expected value. This gives rise to questions such as $E[S_1]=?$ $E[S_t]=?$ $\lim_{t\to \infty}E[S_t]=?$ Is the function $E[S_t]$ monotone decreasing?

(The set of times $t$ in the subscript $S_t$ is the set of ticking times. Because there are infinitely many clocks, every time interval contains infinitely many ticks (with probability $1$). In other words, the ticks are dense in $(0, \infty)$. By the Back-and-forth method, this set is isomorphic (in an sense of order) to the set of positive rational numbers.)

$\mathbf{EDIT:}$ Another possibly solving way: some use of the ergodic theory. Find some ergodic transformation (on the space where each element is the collection of ticking times) and apply an ergodic theorem. Maybe, even using the $S_t$ defined above.

$\endgroup$
3
$\begingroup$

The answer has to be 1. Here is a sketch proof (I don't have a full proof). Construct a graphical model by taking the product of $\mathcal T$ with $\mathbb R^+$. Mark on each copy of $\mathbb R^+$ the times when the clock will ring. At those points in the graphical model, put arrows from the vertex to its neighbors. This allows you, for each $t$ to partition $\mathcal T$ into regions with an ancestor: each region is coloured by following arrows from a unique vertex ("king"). By Borel-Cantelli, each king will be toppled sooner or later, so the root is a subject of a sequence of different kings. This can all be done before the colour of the kings is specified. Your rule is that the original colouring is specified by the parity of the distance from the origin, but it is clear that neither odd nor even is favoured in this model.

$\endgroup$
  • $\begingroup$ Hello Anthony! Thanks for the answer! What do you mean in "This can all be done before the colour of the kings is specified"? $\endgroup$ – co.sine Apr 12 '17 at 7:10
  • $\begingroup$ What I have in mind is that the structure of the transitions (which site colours at time 0 propagate to which site colours at time $t$) can be determined before the colours at time 0 are specified. That is: given a node $v$ and a time $t$, you can determine which nodes at time $t$ end up with the time 0 colour of $v$ without knowing what that colour is. $\endgroup$ – Anthony Quas Apr 12 '17 at 16:57
  • $\begingroup$ OK, agree, this means that the root can be coloured in different colors, depending on the colours at time 0. But how does this induce almost sure divergence? Sorry If I make some mistake. $\endgroup$ – co.sine Apr 13 '17 at 5:11
  • $\begingroup$ I'm not sure if I was clear. What I had in mind was this: (1) leave the base uncoloured for now; but fix the locations of the Poisson clocks. When a Poisson clock rings at vertex $i$, you "cut" the copy of the real line at all of $i$'s neighbours, and put arrows from $i$ to its neighbours (so that at that time, all of the neighbours get the same colour as $i$). Now if you choose any vertex $i$ at any time $t$, you can follow the timeline and arrows backwards to find out which vertex at time 0 gave rise to the colour at $i$. I'm calling that vertex the king ruling over $i$ at time $t$. $\endgroup$ – Anthony Quas Apr 13 '17 at 5:29
  • 1
    $\begingroup$ Sorry. I see I didn't read your question correctly. I didn't see the majority rule part; I just thought the person whose clock rings exports their colour. Not sure now. I will try to think more. $\endgroup$ – Anthony Quas Apr 15 '17 at 15:42

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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