Binary search trees based on Weyl and Lehmer sequences (Q4369769)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1103060
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Binary search trees based on Weyl and Lehmer sequences |
scientific article; zbMATH DE number 1103060 |
Statements
20 April 1998
0 references
random number generators
0 references
linear congruential generators
0 references
Weyl sequences
0 references
Lehmer sequences
0 references
pseudo-random number generation
0 references
binary search tree
0 references
Weyl tree
0 references
continued fraction expansion
0 references
0.902403712272644
0 references
0.7744476795196533
0 references
0.7571748495101929
0 references
0.7420512437820435
0 references
Binary search trees based on Weyl and Lehmer sequences (English)
0 references
The purpose of the study is to amass even more evidence than already exists regarding the inherent dangers of using certain random number generators in simulations. For example, linear congruential generators (based upon the recurrences \(x_n= (ax_n+b)\bmod m\), for \(a\), \(b\), \(m\), \(x_n\) all integer) derive their popularity from easily understood properties of Weyl and Lehmer sequences. As such generators produce integer sequences that are necessarily periodic, they can strictly speaking not be compared with aperiodic sequences such as \(\{n\theta\}\) for \(\theta\) irrational. However, they are fundamental akin to Weyl sequences, which may be obtained by the recurrence \[ x_{n+1}= \{x_n+\theta\}, \qquad x_0=0, \] and Lehmer sequences, which may be obtained by the recurrence \[ x_{n+1}= \{ax_n\}, \qquad x_0\in (0,1). \] We study binary search trees formed by consecutive (standard) insertions of numbers \(\{\theta\}, \{2\theta\}\), \(\{3\theta\},\dots\), where \(\theta\in (0,1)\) is an irrational number, and \(\{\cdot\}\) denotes ``mod 1''. The sequence in question is called the Weyl sequence for \(\theta\), after Weyl, who showed that for all irrational \(\theta\) the sequence is equi-distributed. We recall that a sequence \(x_n\), \(n\geq 1\), is equi-distributed if for all \(0\leq a\leq b\leq 1\), \[ \lim_{n\to\infty} {\textstyle \frac1n} \sum_{i=1}^n I_{x_i\in [a,b]}= b-a. \] The equi-distribution property makes Weyl sequences, or suitable generalizations of them, prime candidates for pseudo-random number generation. Of course, various regularities in the sequence make them rather unsuitable for most purposes. Let \({\mathcal T}_n (\theta)\) be the binary search tree based upon the first \(n\) numbers in the Weyl sequence for \(\theta\). This tree, called the Weyl tree, captures a lot of refined information regarding the structure of the Weyl sequence, and is a fundamental tool for the analysis of algorithms involving Weyl sequences in the input stream. Computer scientists are mostly concerned with the following structural qualities: the average depth of a node (the depth is the path distance from a node to the root), the height (the maximal depth), and the number of leaves (the number of nodes with no children). The discussion in this paper focuses on these quantities. We relate various properties of the structure of these trees to the continued fraction expansion of \(\theta\). If \(H_n\) is the height of the tree with \(n\) nodes when \(\theta\) is chosen at random and uniformly on \([0,1]\), then we show that in probability, \(H_n\sim (12/\pi^2)\log n\log\log n\). We conclude with some properties of binary search trees for Lehmer sequences \(\{x_0a^n\}\) where \(x_0\) is a real number and \(a>1\) is an integer. For the entire collection see [Zbl 0879.00054].
0 references