On the probability of occurence of labelled subtrees of a randomly labelled tree (Q810523): Difference between revisions
From MaRDI portal
Changed an Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0304-3975(89)90040-6 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2031347916 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Connectivity properties of Mandelbrot's percolation process / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Subcritical branching processes in a two-state random environment, and a percolation problem on trees / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Superbranching processes and projections of random Cantor sets / rank | |||
Normal rank |
Latest revision as of 10:10, 24 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the probability of occurence of labelled subtrees of a randomly labelled tree |
scientific article |
Statements
On the probability of occurence of labelled subtrees of a randomly labelled tree (English)
0 references
1989
0 references
For a positive integer b, consider an infinite binary (rooted) tree in which every node has one parent (excepting the root) and exactly b children. Let every node v be assigned with a random variable \(X_ v\), such that \(\{X_ v\}_{v\in V}\) are independent identically distributed binary variables: \[ P(X_ v=0)=1-p,\quad P(X_ v=1)=p. \] Denote by \(\pi_ n(p)\) the probability that each node of level less than n has at least one child assigned with 0 and at least one child assigned with 1. As clearly \(\pi_{n+1}(p)\leq \leq \pi_ n(p)\) there must exist a value \[ \pi_*(p)=\lim_{n\to \infty}\pi_ n(p). \] The main result is the following assertion. Theorem. If \(b\leq 4\) then \(\pi_*(p)=0\) for all \(p\in <0,1>;\) if \(b\geq 5\) then there exists \(p_ c\in (0,\frac12)\) such that \(\pi_*(p)=0\) if \(p<p_ c\) or \(p>1-p_ c,\) and \(\pi_*(p)>0\) for \(p\in <p_ c,1-p_ c>.\)
0 references
binary tree
0 references
random graph
0 references