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

3

This does not compute an exact value but some rigorous upper bounds of the probability $r$ that every site in $\mathbb Z^2$ is reached, eventually.

Consider the Galton-Watson branching process where the progeny of every individual has the distribution of the number of signals transmitted at time $n+1$ by any site reached at time $n$. Thus the progeny of any node in the Galton-Watson tree is $0$, $1$, $2$, $3$ and $4$ with respective probabilities $1$, $4$, $6$, $4$ and $1$ divided by $16$.

Then the generation $n$ of the process overestimates the number of sites reached at time $n$ since the signals received from different neighbors stay separated. Hence the probability $q$ that the tree becomes extinct underestimates the probability that the cloud of sites receiving a signal becomes empty. On the other hand, if the cloud survives forever, the path of any eternally transmitted signal is a simple random walk on $\mathbb Z^2$, and these are recurrent hence every site is reached by the trace of the cloud on the grid, eventually.

The extinction probability $q$ is classically the smallest root in $[0,1]$ of the one-step equation $$ 16q=1+4q+6q^2+4q^3+q^4, $$ which is $q=0.087378$. Hence every site on the grid is reached by the original transmission process with probability $r\lt91.2622\%$.

Now, the probability $r_T$ that $T=(10^5,10^5)$ is reached corresponds to the fact that generation $n=2\cdot10^5$ of the tree is not empty, whose probability $1-q_n$ is very close to $1-q$, hence $r_T\lt1-q_n\approx1-q$.

Nota: One gets a simpler bound noticing that, if the initial site transmits nothing, no other site is reached, and this happens with probability $1/16=6.25\%$, hence $r\lt93.75\%$.

3

In the same vein as Didier's answer providing bounds on the extinction probability $q$, we can also obtain bounds on the transmission probability $p$ required for the probability of $N$ signals dying out to go to $0$ as $N\to\infty$, which is the probability required for the extinction probability $q$ not to be $1$.

Didier's equation for $q$ can be rewritten as $q=(1-(1-q)/2)^4$, which says that the signal goes extinct if all four signals die, either because they don't make it across the edge ($1/2$) or because they go extinct afterwards ($1-q$). Generalizing to $d$ dimensions and transmission probability $p$, this is

$$q=(1-p(1-q))^{2d}\;.$$

This equation always has a root at $1$. For sufficiently large $q$, it also has a second root in $[0,1]$, and the extinction probability is given by that root. The critical case in which the extinction probability becomes $1$ occurs when these two roots coincide. Differentiating with respect to $q$ and substituting $q=1$ yields the condition for $1$ to be a double root:

$$ \begin{eqnarray} 1&=&2dp(1-p(1-q))\;, \\ 1&=&2dp\;, \\ p&=&\frac1{2d}\;. \end{eqnarray} $$

This is a lower bound, since in the case of confluent signals there are fewer signals to keep the fire burning. Your experiments seem to indicate that the bound becomes better with increasing dimension, which makes sense since the signals become less likely to collide.

1

This is not an answer, but was too long for a comment. More like some observations and additional, related questions on the theme of whether generating functions would help.

My particular choice of generating functions model additive signals and therefore could be used as upper bounds for nonadditive ones.

My approach below is probably not original. Good combinatorial interpretations probably already exist. This is a Galton-Watson stochastic branching process.

The one-dimensional case has generating function in the formal power series ring with indeterminates $x,x^{-1}$ (or its quotient with the ideal $\left< x^{-1}x-1 \right>$) given by $$ \eqalign{ p_t^*(x) &= p^t \left(x+x^{-1}\right)^t = p^t \sum_{s=0}^{t} {t \choose s} x^{2s-t} = p^t \sum_{s=0}^{t} {t \choose s} x^{t-2s} \cr & = p^t \left( \left\lfloor\tfrac{t}2\right\rfloor- \left\lfloor\tfrac{t-1}2\right\rfloor \right) {t \choose t/2} + p^t \sum_{s=0}^{\left\lfloor\tfrac{t-1}2\right\rfloor} {t \choose s} \left(x^{t-2s}+x^{2s-t}\right) } $$ for time $t$, i.e. the coefficient of $x^m$ is the probability the signal reaches coordinate $x=m$ at time $t$. The first term on the second line, the constant term, representing the probability of revisiting the origin, is positive with maximum coefficient for $t$ even, but $0$ for $t$ odd. The differences in parentheses above, $$ e(t)= \left\lfloor\tfrac{t}2\right\rfloor- \left\lfloor\tfrac{t-1}2\right\rfloor = \tfrac{t+1}2-2\left\lfloor \tfrac{t+1}2\right\rfloor =\frac{1+(-1)^{t+1}}{2} =(t+1)~\text{mod}~2 $$ indicates evenness. We could also take the last expression and throw away the (strictly) negative powered terms $x^{2s-t}$, redefining the coefficient of $x^m$ to be the probability that a signal starting at the origin at time $0$ reaches $x=\pm m$ (one or the other) after time $t$, and call this the reduced generating function $$ p_t(x) = p^t \left[ e(t) {t \choose t/2} + \sum_{s=0}^{\left\lfloor\tfrac{t-1}2\right\rfloor} {t \choose s} x^{t-2s} \right]. $$ Note in particular that $e(t){t\choose t/2}$ is therefore the number of paths of length $t$ which start and end at the origin. Summing over $t\ge0$, we get a generating function $$ p(x)=\sum_{t=0}^{\infty} p_t(x) $$ for the expected amount of time spent at each coordinate, i.e. the coefficient of $x^m$ is the sum of probabilities that the signal is at one of $x=\pm m$ over all times $t\ge 0$. Of particular interest to us is the expected total time spent at the origin, $$ p(0)=\sum_{t=0}^\infty{2t\choose t}p^{2t}. $$ Combinatorial note: there is no double-counting (no need for P.I.E.) because each term counts only the terminus point over all paths of length $t$. This acts like a "driving force" of a harmonic oscillator damped by a probability of dying out. By Stirling's approximation and the root test, this converges, for $p<\frac12$.

Claim $\left(\mathbb{Z}^1\right)$: For $r=2p<1$, the expected total number of visits to the origin converges to $$p(0)=\frac{1}{\sqrt{1-r^2}}.$$

Proof: this follows from the general binomial theorem, as in e.g. Yuan 2001 proposition 4.3: $$ \left(-4\right)^n {-\tfrac12 \choose n} = \left(-4\right)^n \frac{(-1)(-3)\cdots(1-2n)}{2^n\,n!} = \frac{(2n)!}{(n!)^2}. $$

Now for the two-dimensional case, we can avoid using the multinomial theorem expansion, if we like, with $$ \eqalign{ p_t^*(x,y) &= p^t \left(x+x^{-1}+y+y^{-1}\right)^t = \sum_{s=0}^{t} {t \choose s} p_s^*(x) \, p_{t-s}^*(y) \cr &= p^t \sum_{s=0}^{ t } \sum_{u=0}^{ s } \sum_{v=0}^{t-s} { t \choose s} { s \choose u} {t-s\choose v} x^{2u-s} y^{2v+s-t} } $$ or, throwing away the negative powered terms, $$ \eqalign{ p_t(x,y) &= \sum_{s=0}^{t} {t \choose s} p_s(x) \, p_{t-s}(y) %% %% This formula could be simplified analogously to p_t^*(x) above: %% %\cr %&= p^t % \sum_{s=0}^{ t } % \sum_{u=0}^{ s } % \sum_{v=0}^{t-s} % { t \choose s} % { s \choose u} % {t-s\choose v} % x^{2u-s} y^{2v+s-t} } $$ and take the analogous sum $p(x,y)$. Note that $p_t(0,0)=0$ for odd $t$, and that (for $2t$ even) $$ p_{2t}(0,0) =p^{2t}\sum_{s=0}^t{2t\choose 2s}{2s\choose s}{2t-2s\choose t-s} =p^{2t}\sum_{s=0}^t{t\choose s}^2 =p^{2t}{2t\choose 2}^2 $$ which is $p^t$ times the square of a central binomial coefficient; cf. sequence A000984. (The latter two formulas, with the squared binimial coefficients, are offered here without proof.) Hence $$ p(0,0)=\sum_{t=0}^\infty{2t\choose t}^2p^{2t}, $$ which will converge for $p<\frac14$.

Claim $\left(\mathbb{Z}^2\right)$: For $r=4p<1$, the expected total number of visits to the origin converges to $$p(0,0)={}_2F_1\left(\tfrac12;\tfrac12;1;r^2\right)=\frac1{M(1,\sqrt{1-r^2})}$$ converges to a special case of the Gaussian hypergeometric series ${}_2F_1$ which is a complete elliptic integral of the first kind and can be calculated with extremely rapid convergence (Gauss 1799) by the arithmetic-geometric mean $$M(a,b)=\int_0^{\frac\pi2}\frac{d\phi}{\sqrt{(a\cos\phi)^2+(b\sin\phi)^2}}.$$

The first OP question is perhaps related to the expected time $$ c_{mn} = \mathbb{E} \left[ T_{mn} \right] = \frac1{m!\,n!} \left. \left( \partial_x^{\,m} \partial_y^{\,n} p(x,y) \right) \right|_{(0,0)} \qquad(m,n\ge0) $$ spent at one of the four points $(\pm m,\pm n)$ which is the sum of the $x^my^n$ terms over all $p_t(x,y)$ and can be computed deterministically with no further simplification in $O(m^3n^3)$ time by adding products of binomial coefficients. Perhaps there are ways to simplify this using some combination of binomial identities, parity and symmetry, or with asymptotics, to get a reasonable approximation in a feasible amount of time.

The familiar formula with the higher order derivative using the Taylor series trick for the desired coefficient is valid on the reduced generating function for $m,n\ge 0$.

As a wild speculation, is the answer to the (first and) second OP question then $$ \frac{c_{mn}}{1-p(0,0)} $$ or something in a similar vein, analogously to the gambler's ruin problem or the reasoning of @joriki or @Didier?

Conjectures for higher dimensions:

Conjecture: The expected number of visits to the origin in $\mathbb{Z}^d$ is $$ \sum_{n=0}^\infty {2n \choose n}^d p^{2n}. $$

Conjecture: The number of paths in $\mathbb{Z}^d$ of length $2n$ which start and end at the origin is $$ {2n \choose n}^d. $$ Note: $d=2$ is Richard Stanley's bijective proof problem #230.

  • 0
    Why do you wonder only for the third question whether signals are additive or sub-additive? It seems that in your entire analysis you assume that they're additive, which would mean that your results are bounds for the sub-additive case, like Didier's and mine.2012-02-23
  • 0
    @joriki: yes, of course. thanks.2012-02-23
  • 0
    The conjectures at the end of your post are well known for $d=2$ (as you write) and wrong for $d\geqslant3$.2012-03-01
1

This may be too simplistic, and I only get a $71.0\%$ result. I assume that around the node $(10^5,10^5)$ all the neighboring nodes have the same probability of being reached, call it $P$ to distinguish it from the $p$ in the question.

One other assumption: transmissions works $1/2$ the time.

        *

   *    *    *
       (a,a)

        *

So $(a,a)$ could receive it from any of the four neighbors.

At each of the neighbor nodes I use the conditional probability that the node receives the signal before the center node $(a,a)$ does. I assume that equals $.75P$ since the neighbor node then did not receive the signal from $(a,a)$.

Then I have the following equation using the binomial probability formula

$$\binom{4}{1} (.75 P) (1-.75P)^3(1-0.5)+ \binom{4}{2} (.75P)^2 (1-.75P)^2 (1-.25)+ \binom{4}{3} (.75)^3 (1-.75P) (1-.125)+ \binom{4}{3} (.75)^4 (1-.0625) = P$$

Solving, $P \approx .703$.

This approach fails when close to the origin, I think.

  • 2
    At least two problems here -- a minor one: why is the fourth term $\binom44(.75)^4(1-.75P)^0(1-1/16)$ missing? And a major one: The assumption "A node transmits the signal at most once on each of its four links." couldn't be further from the truth. The situation has an almost-$0$-$1$ character; the signal either dies out quickly or snowballs, and if it snowballs, there are signals all over the place. The event that the node receives the signal exactly once on any of its four links in fact has probability close to $0$.2012-02-22
  • 0
    Hi joriki, I misread a sentence in the problem. However I corrected these and now I get a great answer, but now I am going to check some of the other simulation results. I have experience with communication networks. There you do not want to retransmit the same signal because then you waste network bandwidth on just one signal. That is probably why I misconstrued the original problem.2012-02-22
  • 0
    Well, using .2872 instead of 0.5 didn't work well. My attempt is likely just the same thing as Didier's, jorikis but more clumsy.2012-02-22
  • 0
    Sorry to belabor the topic. But I think Didier and joriki are both making the assumption that a node transmits only once: "Didier's equation for q can be rewritten as q=(1−(1−q)/2)4, which says that the signal goes extinct if all four signals die, either because they don't make it across the edge (1/2) or because they go extinct afterwards (1−q). " Since any node will transmit the signal any number of times, the probability of not making across a given edge is much less than 1/2.2012-02-22
  • 0
    I think you're interpreting that from the viewpoint of your approach. I'm not talking about what happens at $x,y$, but about what happens right at the beginning when there's just a single active node, and I calculate the probability $q$ that it will go extinct from the probability $p$ that its very first signals are transmitted successfully and the probability $q$ that the nodes reached by the successfully transmitted signals will go extinct. That has nothing to do with the fact that if the signal survives long-term, it will reach the original node many (almost surely infinitely many) times.2012-02-23
  • 0
    Does make sense thanks2012-02-23
  • 0
    @Bill: *I think Didier and joriki are both making the assumption that a node transmits only once*... No, I am not (and I see nothing in my post indicating that I would).2012-03-02