This article extends the results of Fang & Zeitouni (2012a) on branching random walks (BRWs) with Gaussian increments in time inhomogeneous environments. We treat the case where the variance of the increments changes a finite number of times at different scales in [0,1] under a slight restriction. We find the asymptotics of the maximum up to an OP(1) error and show how the profile of the variance influences the leading order and the logarithmic correction term. A more general result was independently obtained by Mallein (2015b) when the law of the increments is not necessarily Gaussian. However, the proof we present here generalizes the approach of Fang & Zeitouni (2012a) instead of using the spinal decomposition of the BRW. As such, the proof is easier to understand and more robust in the presence of an approximate branching structure.
One shortfall of the spinal decomposition is that it completely relies on the presence of an branching structure. Specifically, a crucial step in @cite_21 is the proof of a time-inhomogeneous version of the classical many-to-one lemma, which is a direct consequence of his comparison between the size-biased law of the BRW (the usual change of measure) and a certain projection of a law on the set of planar rooted marked trees with spine.
@cite_21
2092349993 2119847065 1998544343 1751486617
Chapter 36 Decomposing Graphs into Regions of Small Diameter* Nathan Linialt Michael .lss A decomposition of a graph G = (V, E) is a partition of the vertex set into subsets (called lhks). The diameter of a decomposition is the least. d such that any two vertices belonging to the same connected component of a block are at distance < d. In this paper we prove (nearly best possible) statements of the form: .4ny n–vertex graph has a decomposition into a small number of blocks each having small diameter. Such decompositions provide a tool for efficiently decentralizing distributed computations. In [AGLP1 it was shown that every graph has a decomposition into at most s(n) blocks of diameter at most s(n) for s(n) = o( loglog d h n). usinga,technique of Awerbuch [A] and Awerbuch and Peleg [AP], we improve this result by showing that every graph has a decomposition of diameter ()(log n) into O(log n) blocks. In addition, we give a randomized distributed algorithm that produces such a decomposition and runs in time 0(log2 n). The construction can be parametrized to provide decompositions that trade-off between the number of blocks and the diameter. We show that this trade-off is nearly best possible for two families of graphs the first consists of skeletons of certain triangulations of a simplex and the second consists of grid graphs with added diagonals. The proofs in both cases rely on basic results in combinatorial topology, Sperner’s lemma for the first class and Tucker’s lemma for the second. *This work was supported in part by NSF contracts DMS87-03541 and CCR-8911388 tDepartment of Computer Science, Hebrew University, Jerusalem, Israel. + ‘Department of Computer Science and Engineering, Mail Code C-014, University of California, San Diego, La Jolla, CA 92093-0114. Abstract Recently Harris [Proc. Roy. Soc. Edinburgh Sect. A 129 (1999) 503], using probabilistic methods alone, has given new proofs for the existence, asymptotics and uniqueness of travelling wave solutions to the K-P-P equation. Following in this vein we outline alternative probabilistic proofs. Specifically the techniques are confined to the study of additive and multiplicative martingales and spinal path decompositions along the lines of [B. Chauvin, A. Rouault, Probab. Theory Related Fields 80 (1988) 299], [R. Lyons, in: K.B. Athreya, P. Jagers (eds.), Classical and Modern Branching Processes, Vol. 84, Springer-Verlag, New York, 1997, pp. 217–222] and [R. , Ann. Probab. 23 (1995) 1125]. We also make use of a new decomposition where the spine is a conditioned process. Some new results concerning martingale convergence are obtained as a by-product of the analysis. Adecomposition of a graphG=(V,E) is a partition of the vertex set into subsets (calledblocks). Thediameter of a decomposition is the leastd such that any two vertices belonging to the same connected component of a block are at distance ≤d. In this paper we prove (nearly best possible) statements, of the form: Anyn-vertex graph has a decomposition into a small number of blocks each having small diameter. Such decompositions provide a tool for efficiently decentralizing distributed computations. In [4] it was shown that every graph has a decomposition into at mosts(n) blocks of diameter at mosts(n) for (s(n) = n^ O( n n) ). Using a technique of Awerbuch [3] and Awerbuch and Peleg [5], we improve this result by showing that every graph has a decomposition of diameterO (logn) intoO(logn) blocks. In addition, we give a randomized distributed algorithm that produces such a decomposition and runs in timeO(log2n). The construction can be parameterized to provide decompositions that trade-off between the number of blocks and the diameter. We show that this trade-off is nearly best possible, for two families of graphs: the first consists of skeletons of certain triangulations of a simplex and the second consists of grid graphs with added diagonals. The proofs in both cases rely on basic results in combinatorial topology, Sperner's lemma for the first class and Tucker's lemma for the second. This paper presents an analysis of spinal codes, a class of rateless codes proposed recently. We prove that spinal codes achieve Shannon capacity for the binary symmetric channel (BSC) and the additive white Gaussian noise (AWGN) channel with an efficient polynomial-time encoder and decoder. They are the first rateless codes with proofs of these properties for BSC and AWGN. The key idea in the spinal code is the sequential application of a hash function over the message bits. The sequential structure of the code turns out to be crucial for efficient decoding. Moreover, counter to the wisdom of having an expander structure in good codes, we show that the spinal code, despite its sequential structure, achieves capacity. The pseudo-randomness provided by a hash function suffices for this purpose. Our proof introduces a variant of Gallager's result characterizing the error exponent of random codes for any memoryless channel. We present a novel application of these error-exponent results within the framework of an efficient sequential code. The application of a hash function over the message bits provides a methodical and effective way to de-randomize Shannon's random codebook construction.