Ascending runs in dependent uniformly distributed random variables: Application to wireless networks

Nathalie Mitton (1) , Katy Paroux (2) , Bruno Sericola (3) , Sébastien Tixeuil (4)

1 POPS - System and Networking for Portable Objects Proved to be Safe
2 LMB - Laboratoire de Mathématiques de Besançon (UMR 6623)
3 DIONYSOS - Dependability Interoperability and perfOrmance aNalYsiS Of networkS
4 GRAND-LARGE - Global parallel and distributed computing

We analyze in this paper the longest increasing contiguous sequence or maximal ascending run of random variables with common uniform distribution but not independent. Their dependence is characterized by the fact that two successive random variables cannot take the same value. Using a Markov chain approach, we study the distribution of the maximal ascending run and we develop an algorithm to compute it. This problem comes from the analysis of several self-organizing protocols designed for large-scale wireless sensor networks, and we show how our results apply to this domain.

Mots clés: Markov chains; maximal ascending run; self-stabilization; convergence time

Domaines: Mathématique discrète [cs.DM]; Réseaux et télécommunications [cs.NI]; Combinatoire [math.CO]; Probabilités [math.PR]

Nathalie Mitton, Katy Paroux, Bruno Sericola, Sébastien Tixeuil. Ascending runs in dependent uniformly distributed random variables: Application to wireless networks. [Research Report] RR-6443, INRIA. 2008, pp.12. ⟨inria-00239348v5⟩