Uniform recursive trees: branching structure and simple random downward walk (Q819045): Difference between revisions
From MaRDI portal
Latest revision as of 11:20, 24 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Uniform recursive trees: branching structure and simple random downward walk |
scientific article |
Statements
Uniform recursive trees: branching structure and simple random downward walk (English)
0 references
22 March 2006
0 references
Starting with a single node called the root and labeled 1, a random tree with \(k+1\) labeled nodes is recursively defined from the tree with \(k\) labeled nodes by joining a new node labeled \(k+1\) to a randomly chosen previous node for \(k=1,2,\dots\). The random recursive tree with \(n\) nodes has a uniform probability distribution on \((n-1)!\) different labeled rooted trees. The branches of the tree are the remaining connected components when the root is removed. The probability distribution of the frequencies of branches of different sizes \(1,2,\dots,n-1\) is determined, and its limiting properties are studied for increasing \(n\). The results are used to investigate the length of a random walk from the root.
0 references
distribution of branches
0 references
random walk
0 references
local search
0 references
epidemiology
0 references
0 references