11
$\begingroup$

Consider $\mathbb{Z}^2$ as a graph, where each node has four neighbours. 4 signals are emitted from $(0,0)$ in each of four directions (1 per direction) . A node that receives one signal (or more) at a timestep will re-emit it along the 4 edges to its four neighbours at the next time step. A node that did not receive a signal at the previous timestep will not emit a signal irrespective of whether it earlier received a signal. There is a $50\%$ chance that a signal will be lost when travelling along a single edge between two neighbouring nodes. A node that receives more then 1 signal acts the same as if it received only 1. The emitting of a signal in each of the 4 directions are independent events.

What is the probability that the signal will sometime arrive at $(10^5,10^5)$? Research: Simulations show: Yes. ~90%

What is the probability that the signal will sometime arrive at $(x,y)$ if a signal traveling along an edge dies with probability $0?

What is the least p, for which the probability that N initial random live cells die out approaches 0, as N approaches infinity? Experiment shows p close to 0.2872.

In $\mathbb{Z}^1$, $p_{min}=0.6445...$, how to calculate this?

In $\mathbb{Z}^3$, $p_{min}=0.1775...$, how to calculate this?

  • 0
    What did you try? What similar problem(s) do you know? What tools were introduced to you that are related to this problem? Is this homework?2012-02-21
  • 9
    Hmmm... So this problem comes out of the blue, you know NOTHING similar, you tried NOTHING, you reached NO partial result of any kind?2012-02-21
  • 1
    What is the probability that all four message going out of $(0,0)$ are lost, and so nothing is happening in the network thereafter?2012-02-21
  • 3
    The probability $\gt90\%$ that you mention should be very close to the non-zero real root of $1-p=(1-p/2)^4$, which is $$p = \frac23 \left(4-\frac2{\sqrt[3]{3 \sqrt{33}-17}}+\sqrt[3]{3 \sqrt{33}-17}\right)\approx0.912622\;.$$2012-02-21
  • 0
    OK, so here are some questions on your updates: what simulations exactly did you perform in the $p=1/2$ case for the probability to reach target $T=(10^5,10^5)$? The [revisions of the post](http://math.stackexchange.com/posts/111700/revisions) show that $\gt90\%$ was previously $\gt95\%$, what made you change this estimate? More to the point: if I understand the model correctly, during a run of the simulation, one has to keep track of the entire cloud of sites alive at each step since any of these could prove to be the source of the message reaching $T$. I wonder how you do that.2012-02-21
  • 0
    @DidierPiau You understood correctly. I didnt check if it reaches exactly that point, either the cells die within a few iterations or they grow without bound.2012-02-21
  • 0
    I'm wondering about how exactly you're doing this. In the description in the first paragraph, it sounds like the signals are independent of each other, but later when you talk about "live cells", I wonder whether a node only emits at most one signal per time step. That would explain your critical values, which I would have thought should be $1/(2d)$ for independent signals (where $d$ is the dimension).2012-02-21
  • 0
    @joriki A node emits up to 2d signals at a timestep, each an independent event. But a cell can receive signals from 2d nodes aswell. A cell deactivates at each timestep, unless it receives a signal.2012-02-22
  • 0
    That's what I suspected: If a node can only emit up to $2d$ signals per time step, then you're not treating each signal as independent. If that's what you intended, you should adapt the first paragraph. It sounds as if each signal is a separate entity, and if a node receives two signals simultaneously, it will re-emit *both* of them in the next time step, which could lead to a node emitting more than $2d$ signals in a time step. (See also the question at the end of bgins' answer.)2012-02-22
  • 1
    Why is this CW?2012-02-22
  • 0
    @cardinal: See http://meta.stackexchange.com/questions/11740/what-are-community-wiki-posts ("How does a post become a Community Wiki post?"): "Posts enter community wiki mode when [... t]he post has been edited ten (10) times by the original owner."2012-02-22
  • 0
    @LLLLL: Thanks for the clarification about multiple received signals. I don't know why you're considering this problem (you didn't tell us), but if the context allows you to consider the problem with completely independent signals instead, I think you'll find the analysis a bit easier in that case.2012-02-22
  • 0
    @LLLLL You are still remarkably silent about the practical details of the simulations that allow you to reach lower bounds such as $\gt90\%$ (not to mention error bars) on probabilities related to random processes whose values are subsets of the grid, finite but whose size is a priori unlimited.2012-02-22
  • 0
    @Didier: 10 edits? I knew this rule, but what on earth has been going on with this question? Wow.2012-02-22
  • 1
    @cardinal: Indeed... :-) Now 21 edits due to the OP, but still zero explanation about the (claimed) simulations. To tell the truth, I have never seen simulations that could yield in succession $\gt95\%$, then $\gt90\%$, then (but only after I proved the result is at most $91.3\%$) $\sim90\%$...2012-02-22

4 Answers 4