Patrick Erik BradleyUltrametricity indices for the Euclidean and Boolean hypercubesAbstract
Motivated by Murtagh's experimental observation that sparse random samples
of the hypercube
become more and more ultrametric as the dimension increases, we
prove that his ultrametricity index as well as our topological ultrametricity index
converges in probability to one as dimension increases, if the sample size remains
fixed. This is done for uniformly and normally distributed samples in the Euclidean
hypercube, and for uniformly distributed samples in $\mathds{F}_2^N$
with Hamming distance, as well as for uniform random categorial data in complete
disjunctive form. A second result is that both ultrametricity indices vanish in the
limit for the full hypercube $\mathds{F}_2^N$ as dimension $N$ increases, whereby
Murtagh's ultrametricity index is greater than the topological ultrametricity index
if $N$ is large.
