The Hierarchical Way — Two Ways of Measuring

The Infinite Tree

Recall branching nesting: at each level, a container holds $b$ alternative sub-containers. This structure is the infinite $b$-ary tree $T_b$. From a root, $b$ branches emerge. From each child, $b$ more. Forever.

A point in this space is an infinite path from the root — a sequence of digits $v = a_0 a_1 a_2 \ldots$, where each $a_i \in \{0, 1, \ldots, b-1\}$. This sequence is the point's address.

Interactive Tree Explorer

Click Nodes to Measure Tree Distance

Click two nodes to measure the tree distance between them

Each node is a vertex in the binary tree. Its label is its path from the root (a binary sequence). Two nodes are close if they share a long common prefix — they only diverged recently. They are far if they diverge near the root. Distance is $2^{-k}$ where $k$ is the shared prefix length.

Tree Distance: Formal Definition

Definition (Common prefix length). For two points $v, w \in T_b$, the common prefix length $k(v, w)$ is the largest $k$ such that $a_i = b_i$ for all $i < k$. If they differ at the first digit, $k = 0$. If they are identical, $k = \infty$.

Definition (Tree distance). $d_T(v, w) = b^{-k(v, w)}$, with $b^{-\infty} = 0$.

Worked Examples ($b = 2$)

$v$	$w$	Prefix $k$	Distance
$000\ldots$	$001\ldots$	$2$	$2^{-2} = 0.25$
$01011\ldots$	$01010\ldots$	$4$	$2^{-4} = 0.0625$
$000\ldots$	$111\ldots$	$0$	$2^{0} = 1$ (max)
$1010101010\ldots$	$1010101011\ldots$	$9$	$2^{-9} \approx 0.002$

The Strong Triangle Inequality

Theorem (Ultrametric Inequality)

For any three points $x, y, z$ in $T_b$:

$$d_T(x, z) \leq \max\!\bigl(d_T(x, y),\; d_T(y, z)\bigr)$$

This is stronger than the ordinary triangle inequality $d(x,z) \leq d(x,y) + d(y,z)$. Instead of the sum, it uses the maximum. The strong inequality implies the ordinary one.

Click to expand proof

Let $k(x,y)$ be the common prefix length. The key observation:

$$k(x, z) \geq \min(k(x, y), k(y, z))$$

Why? If $x$ and $y$ agree for $p$ digits, and $y$ and $z$ agree for $q$ digits, then $x$ and $z$ agree for at least $\min(p,q)$ digits (agreement is transitive).

Since $t \mapsto b^{-t}$ is strictly decreasing:

$$d_T(x,z) = b^{-k(x,z)} \leq b^{-\min(k(x,y),k(y,z))} = \max(b^{-k(x,y)}, b^{-k(y,z)}) = \max(d_T(x,y), d_T(y,z))$$

The No-Accumulation Property

Theorem (No Accumulation)

In an ultrametric space, if $d(x, y) < T$ and $d(y, z) < T$, then $d(x, z) < T$.

Interpretation: You cannot accumulate small steps to cross a threshold. A thousand errors of size $0.001$ produce a total error of at most $0.001$ — not $1.0$. This is the direct opposite of the continuous case. It is an exact theorem, not an approximation.

Scenario	Continuous ($\mathbb{R}$)	Hierarchical ($T_b$)
1,000 errors of size 0.001	Total error ≤ 1.0	Total error ≤ 0.001
Errors accumulate?	Yes (add)	No (bounded by max)

Geometric Consequences

Every Triangle Is Isosceles

In an ultrametric space, for any three points, the two largest distances are equal. You cannot have a scalene triangle — the geometry is rigid.

Proximity Is Transitive

"Close to" below any fixed threshold is an equivalence relation. Points either share a cluster or they don't — there is no "kind of close."

Strictly Nested, Disjoint Clusters

At threshold $T = b^{-d}$, the space partitions into exactly $b^d$ disjoint clusters. Clusters at different depths are either disjoint or one is entirely inside another — never partially overlapping.