Teoriya Veroyatnostei i ee Primeneniya
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor
Guidelines for authors
Submit a manuscript

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Teor. Veroyatnost. i Primenen.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Teoriya Veroyatnostei i ee Primeneniya, 1993, Volume 38, Issue 2, Pages 453–457 (Mi tvp3956)  

This article is cited in 1 scientific paper (total in 1 paper)

Short Communications

Distribution of the height of a random tree with labeled edges

B. A. Sevast'yanov

Steklov Mathematical Institute, Russian Academy of Sciences
Full-text PDF (306 kB) Citations (1)
Abstract: A random genealogical tree of n generations of a supercritical Galton-Watson branching process with generating function $h(s)$, $h(0)=0$, $h'(1)=A>1$, is considered; the $t$th level of vertices of the tree corresponds to the particles of the $t$th generation. Edges of the tree are labelled by independent and identically distributed random variables $\{\xi_\alpha\}$ with distribution function $G(x)=\mathbf{P}\{\xi_\alpha\le x\}$. The weight of the path from the root to a vertex of the $n$th level is defined as the sum of labels $\xi_\alpha$ of all the edges of this path. The height $\eta_n$ of the tree is the maximum weight over all such paths. It is shown that the distribution function $F_n(x)=\mathbf{P}\{\eta_n<x\}$ satisfies the recursion relation
$$ F_{n+1}(x) = h({F_n*G(x)}),\qquad n\ge1,\quad F_1(x)=h(G(x)). $$
It is proved that if $G(x)$ is a bounded lattice distribution with $G(x_0)=1$ and $q=G(x_0)-G(x_0-1)>0$, $Aq>1$ then $\lim_{n\to\infty} \mathbf{P}\{nx_0-\eta_n=kl\}$ exists for any $k=0,1,2,\ldots$, where $l$ is the lattice span.
Keywords: Galton–Watson branching process, random tree with labeled edges, the height of a random tree, supercritical process, Bellman–Harris branching process, branching random walk.
Received: 20.05.1992
English version:
Theory of Probability and its Applications, 1993, Volume 38, Issue 2, Pages 379–382
DOI: https://doi.org/10.1137/1138035
Bibliographic databases:
Document Type: Article
Language: Russian
Citation: B. A. Sevast'yanov, “Distribution of the height of a random tree with labeled edges”, Teor. Veroyatnost. i Primenen., 38:2 (1993), 453–457; Theory Probab. Appl., 38:2 (1993), 379–382
Citation in format AMSBIB
\Bibitem{Sev93}
\by B.~A.~Sevast'yanov
\paper Distribution of the height of a random tree with labeled edges
\jour Teor. Veroyatnost. i Primenen.
\yr 1993
\vol 38
\issue 2
\pages 453--457
\mathnet{http://mi.mathnet.ru/tvp3956}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=1317990}
\zmath{https://zbmath.org/?q=an:0807.60013}
\transl
\jour Theory Probab. Appl.
\yr 1993
\vol 38
\issue 2
\pages 379--382
\crossref{https://doi.org/10.1137/1138035}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=A1993NY72300016}
Linking options:
  • https://www.mathnet.ru/eng/tvp3956
  • https://www.mathnet.ru/eng/tvp/v38/i2/p453
  • This publication is cited in the following 1 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Теория вероятностей и ее применения Theory of Probability and its Applications
    Statistics & downloads:
    Abstract page:196
    Full-text PDF :51
    First page:10
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024