A min-type stochastic fixed-point equation related to the smoothing transformation

Gerold Alsmeyer ; Matthias Meiners

Teoriâ slučajnyh processov, Tome 15 (2009) no. 2, pp. 19-41.

Résumé

This paper is devoted to the study of the stochastic fixed-point equation \begin{equation*} X\ \stackrel{d}{=}\ \inf_{i \geq 1: T_i > 0} X_i/T_i \end{equation*} and the connection with its additive counterpart $X\stackrel{d}{=}\sum_{i\ge 1}T_{i}X_{i}$ associated with the smoothing transformation. Here $\stackrel{d}{=}$ means equality in distribution, $T := (T_i)_{i \geq 1}$ is a given sequence of non-negative random variables, and $X, X_1, \ldots$ is a sequence of non-negative i.i.d. random variables independent of $T$. We draw attention to the question of the existence of non-trivial solutions and, in particular, of special solutions named $\alpha$-regular solutions $(\alpha>0)$. We give a complete answer to the question of when $\alpha$-regular solutions exist and prove that they are always mixtures of Weibull distributions or certain periodic variants. We also give a complete characterization of all fixed points of this kind. A disintegration method which leads to the study of certain multiplicative martingales and a pathwise renewal equation after a suitable transform are the key tools for our analysis. Finally, we provide corresponding results for the fixed points of the related additive equation mentioned above. To some extent, these results have been obtained earlier by Iksanov.

Détail

Keywords: Branching random walk; elementary fixed points; multiplicative martingales; smoothing transformation; stochastic fixed-point equation.

Bibliographie

[1] D. Aldous, A. Bandyopadhyay, “A survey of max-type recursive distributional equations”, Ann. Appl. Probab., 15 (2005), 1047–1110

[2] D. Aldous, J. M. Steele, “The objective method: Probabilistic combinatorial optimization and local weak convergence”, Probability on Discrete Structures, Encyclopaedia of Mathematical Sciences, 110, ed. H. Kesten, Springer, New York, 2003, 1–72

[3] G. Alsmeyer, A. Iksanov, “A log-type moment result for perpetuities and its application to martingales in the supercritical branching random walk”, Electron. J. Probab., 14 (2009), 289–313

[4] G. Alsmeyer, M. Meiners, “A stochastic fixed-point equation related to game-tree evaluation”, J. Appl. Probab., 44 (2007), 586–606

[5] G. Alsmeyer, U. Rösler, “A stochastic fixed-point equation related to weighted branching with deterministic weights”, Electron. J. Probab., 11 (2006), 27–56

[6] G. Alsmeyer, U. Rösler, “A stochastic fixed-point equation related to weighted minima and maxima”, Ann. Inst. H. Poincaré, 44 (2008), 89–103

[7] J. D. Biggins, “Martingale convergence in the branching random walk”, J. Appl. Probab., 14 (1977), 25–37

[8] J. D. Biggins, “Lindley-type equations in the branching random walk”, Stoch. Proc. Appl., 75 (1998), 105–133

[9] J. D. Biggins, A. E. Kyprianou, “Seneta-Heyde norming in the branching random walk”, Ann. Probab., 25 (1997), 337–360

[10] J. D. Biggins, A. E. Kyprianou, “Fixed points of the smoothing transform: the boundary case”, Electron. J. Probab., 10 (2005), 609–631

[11] A. Caliebe, “Representation of fixed points of a smoothing transformation”, Mathematics and Computer Science III, Trends in Math., eds. M. Drmota et al., Birkhäuser, Basel, 2004, 311–324

[12] L. Devroye, “On the probabilistic worst-case time of “Find””, Algorithmica, 31 (2001), 291–303

[13] R. Durrett, T. M. Liggett, “Fixed points of the smoothing transformation”, Z. Wahrsch. verw. Gebiete, 64 (1983), 275–301

[14] W. Feller, An Introduction to Probability Theory and its Applications, v. II, 2nd Edition, Wiley, New York, 1971

[15] Y. Guivarc'h, “Sur une extension de la notion semi-stable”, Ann. Inst. H. Poincaré, 26 (1990), 261–285

[16] A. Iksanov, “Elementary fixed points of the BRW smoothing transforms with infinite number of summands”, Stoch. Proc. Appl., 114 (2004), 27–50

[17] P. Jagers, U. Rösler, “Stochastic fixed points for the maximum”, Mathematics and Computer Science III, Trends Math., eds. M. Drmota et al., Birkhäuser, Basel, 2004, 325–338

[18] Q. Liu, “Fixed points of a generalized smoothing transformation and applications to the branching random walk”, Adv. Appl. Probab., 30 (1998), 85–112

[19] R. Lyons, “A simple path to Biggins' martingale convergence for branching random walk”, Classical and Modern Branching Processes, IMA Vol. Math. Appl., 84, eds. K. B. Athreya, P. Jagers, Springer, New York, 1997, 217–221

[20] M. Meiners, “Weighted branching and a pathwise renewal equation”, Stoch. Proc. Appl., 119:8 (2009), 2579–2597

[21] R. Neininger, L. Rüschendorf, “Analysis of algorithms by the contraction method: additive and max-recursive sequences”, Interacting Stochastic Systems, Springer, Berlin–Heidelberg, 2005, 435–450

[22] L. Rüschendorf, “On stochastic recursive equations of sum and max type”, J. Appl. Probab., 43 (2006), 687–703

[23] G. Samorodnitsky, M. S. Taqqu, Stable Non-Gaussian Random Processes: Stochastic Models with Infinite Variance, Chapman Hall, New York, 1994