We consider three different schemes for signal routing on a tree. The vertices of the tree represent transceivers that can transmit and receive signals, and are equipped with i.i.d. weights representing the strength of the transceivers. The edges of the tree are also equipped with i.i.d. weights, representing the costs for passing the edges. For each one of our schemes, we derive sharp conditions on the distributions of the vertex weights and the edge weights that determine when the root can transmit a signal over arbitrarily large distances.
Probability on trees has been a very active field of probability for the last decades; see e.g. @cite_6 for an introduction and @cite_10 for a recent account. The work here is closely related to first passage percolation on trees and tree-indexed Markov chains, see e.g. @cite_5 @cite_8 . We also rely on results and techniques for branching random walks, see @cite_9 . Transceiver networks have previously been analyzed in the probability literature in the context of spatial Poisson processes, see @cite_3 , but the setup there is quite different from ours.
@cite_8 @cite_9 @cite_6 @cite_3 @cite_5 @cite_10
121824094 2167064216 2101723786 2038983716
Starting around the late 1950s, several research communities began relating the geometry of graphs to stochastic processes on these graphs. This book, twenty years in the making, ties together research in the field, encompassing work on percolation, isoperimetric inequalities, eigenvalues, transition probabilities, and random walks. Written by two leading researchers, the text emphasizes intuition, while giving complete proofs and more than 850 exercises. Many recent developments, in which the authors have played a leading role, are discussed, including percolation on trees and Cayley graphs, uniform spanning forests, the mass-transport technique, and connections on random walks on graphs to embedding in Hilbert space. This state-of-the-art account of probability on networks will be indispensable for graduate students and researchers alike. Probability theory, like much of mathematics, is indebted to physics as a source of problems and intuition for solving these problems. Unfortunately, the level of abstraction of current mathematics often makes it difficult for anyone but an expert to appreciate this fact. In this work we will look at the interplay of physics and mathematics in terms of an example where the mathematics involved is at the college level. The example is the relation between elementary electric network theory and random walks. Central to the work will be Polya’s beautiful theorem that a random walker on an infinite street network in d-dimensional space is bound to return to the starting point when d = 2, but has a positive probability of escaping to infinity without returning to the starting point when d ≥ 3. Our goal will be to interpret this theorem as a statement about electric networks, and then to prove the theorem using techniques from classical electrical theory. The techniques referred to go back to Lord Rayleigh, who introduced them in connection with an investigation of musical instruments. The analog of Polya’s theorem in this connection is that wind instruments are possible in our three-dimensional world, but are not possible in Flatland (Abbott [1]). The connection between random walks and electric networks has been recognized for some time (see Kakutani [12], Kemeny, Snell, and We develop a criterion for transience for a general model of branching Markov chains. In the case of multi-dimensional branching random walk in random environment (BRWRE) this criterion becomes explicit. In particular, we show that Condition L of Comets and Popov [3] is necessary and sufficient for transience as conjectured. Furthermore, the criterion applies to two important classes of branching random walks and implies that the critical branching random walk is transient resp. dies out locally. Suppose that i.i.d. random variables are attached to the edges of an infinite tree. When the tree is large enough, the partial sumsSσ along some of its infinite paths will exhibit behavior atypical for an ordinary random walk. This principle has appeared in works on branching random walks, first-passage percolation, and RWRE on trees. We establish further quantitative versions of this principle, which are applicable in these settings. In particular, different notions of speed for such a tree-indexed walk correspond to different dimension notions for trees. Finally, if the labeling variables take values in a group, then properties of the group (e.g., polynomial growth or a nontrivial Poisson boundary) are reflected in the sample-path behavior of the resulting tree-indexed walk.