On the probability of occurence of labelled subtrees of a randomly labelled tree
type: Item
instance of: scholarly article
title: On the probability of occurence of labelled subtrees of a randomly labelled tree
zbMATH Open document ID: 0734.05043
DOI: 10.1016/0304-3975(89)90040-6
published in: Theoretical Computer Science
publication date: 1989-01-01T00:00:00Z
review text: 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>.\)
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 05C78
Mathematics Subject Classification ID: 60C05
zbMATH DE Number: 4214029
zbMATH Keywords: binary tree
zbMATH Keywords: random graph
author: F. Michel Dekking
reviewed by: Radim Jiroušek
MaRDI profile type: Publication
full work available at URL: 0304-3975(89)90040-6
OpenAlex ID: W2031347916
cites work: Connectivity properties of Mandelbrot's percolation process
cites work: Subcritical branching processes in a two-state random environment, and a percolation problem on trees
cites work: Superbranching processes and projections of random Cantor sets
description: scientific article; zbMATH DE number 4214029