Skip to main content
Bounty Ended with 50 reputation awarded by co.sine
added more details
Source Link
domotorp
  • 19.1k
  • 3
  • 59
  • 128

Yes, my example is easy to modify after some thought, just take a thick enough layer for each level. More precisely, let $f$ be a sufficiently fast growing function, and define the initial value on any vertex at distance $f(n)\le d< f(n+1)$ from the root as $(-1)^n$. Given $f(n)$, one can also pick a large enough $f(n+1)$ such that independently of the later values the root will get $(-1)^n$ in some time that depends only on $f(n+1)$ with at least $50\%$ probability. This guarantees that with $1$ probability it will switch values infinitely often (just like every other vertex).

In more details, suppose first that $f(n+1)=\infty$, i.e., all but a finite number of vertices have the value $(-1)^n$.

Lemma. If all vertices at distance $>r$ have value $(-1)^n$, then with probability $1$ after a while all vertices will have value $(-1)^n$.

Proof. Vertices further than $r$ can never change value. If a vertex at distance $r$ gets value $(-1)^n$, it will never change again. So eventually all vertices at distance $r$ will also obtain value $(-1)^n$ and we can use induction on $r$.

From this it follows that the root will obtain value $(-1)^n$ in some $T(n)$ time with $90\%$ probability. If $f(n+1)$ is not $\infty$, but just large enough compared to $T(n)$, then the probability of any vertex at distance $r+1$ from the root changing value is less than $10\%$. Therefore, this won't affect the probability of the root changing value.

Yes, my example is easy to modify after some thought, just take a thick enough layer for each level. More precisely, let $f$ be a sufficiently fast growing function, and define the initial value on any vertex at distance $f(n)\le d< f(n+1)$ from the root as $(-1)^n$. Given $f(n)$, one can also pick a large enough $f(n+1)$ such that independently of the later values the root will get $(-1)^n$ in some time that depends only on $f(n+1)$ with at least $50\%$ probability. This guarantees that with $1$ probability it will switch values infinitely often (just like every other vertex).

Yes, my example is easy to modify after some thought, just take a thick enough layer for each level. More precisely, let $f$ be a sufficiently fast growing function, and define the initial value on any vertex at distance $f(n)\le d< f(n+1)$ from the root as $(-1)^n$. Given $f(n)$, one can also pick a large enough $f(n+1)$ such that independently of the later values the root will get $(-1)^n$ in some time that depends only on $f(n+1)$ with at least $50\%$ probability. This guarantees that with $1$ probability it will switch values infinitely often (just like every other vertex).

In more details, suppose first that $f(n+1)=\infty$, i.e., all but a finite number of vertices have the value $(-1)^n$.

Lemma. If all vertices at distance $>r$ have value $(-1)^n$, then with probability $1$ after a while all vertices will have value $(-1)^n$.

Proof. Vertices further than $r$ can never change value. If a vertex at distance $r$ gets value $(-1)^n$, it will never change again. So eventually all vertices at distance $r$ will also obtain value $(-1)^n$ and we can use induction on $r$.

From this it follows that the root will obtain value $(-1)^n$ in some $T(n)$ time with $90\%$ probability. If $f(n+1)$ is not $\infty$, but just large enough compared to $T(n)$, then the probability of any vertex at distance $r+1$ from the root changing value is less than $10\%$. Therefore, this won't affect the probability of the root changing value.

Source Link
domotorp
  • 19.1k
  • 3
  • 59
  • 128

Yes, my example is easy to modify after some thought, just take a thick enough layer for each level. More precisely, let $f$ be a sufficiently fast growing function, and define the initial value on any vertex at distance $f(n)\le d< f(n+1)$ from the root as $(-1)^n$. Given $f(n)$, one can also pick a large enough $f(n+1)$ such that independently of the later values the root will get $(-1)^n$ in some time that depends only on $f(n+1)$ with at least $50\%$ probability. This guarantees that with $1$ probability it will switch values infinitely often (just like every other vertex).