Local extrema in random trees
Author(s) -
Lane Clark
Publication year - 2005
Publication title -
international journal of mathematics and mathematical sciences
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.21
H-Index - 39
eISSN - 1687-0425
pISSN - 0161-1712
DOI - 10.1155/ijmms.2005.3867
Subject(s) - algorithm , artificial intelligence , computer science
The number of local maxima (resp., local minima) in a tree T∈n rooted at r∈[n] is denoted by Mr(T) (resp., by mr(T)). We find exact formulas as rational functions of n for the expectation andvariance of M1(T) and mn(T) when T∈n is chosenrandomly according to a uniform distribution. As a consequence,a.a.s. M1(T) and mn(T) belong to a relatively small intervalwhen T∈n
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom