Average height of the least common ancestor of 2 random nodes in a binary tree
It took me a while to see the nice formula, but there is one.
Consider a node $w$ at height $k$. The root is at height $h$ and the leaves at height $1$.

The probability that $w$ is the least common ancestor of the two nodes is the probability that:


  (1) Both random nodes are in the subtree rooted at $w$;


and we do not have that


  (2) Both nodes are in $w$'s left subtree or both nodes are in $w$'s right subtree.


The size of a subtree at height $k$ is $2^k-1$.
The probability of #1 is therefore $\left(\frac{2^k-1}{2^h - 1}\right)^2$. The probability of #2 is $2 \left(\frac{2^{k-1}-1}{2^h - 1}\right)^2$.

The probability of the event that #1 happens and #2 does not (since #2 is a subset of #1) is thus
\begin{align}
\Pr[\text{$w$ at height $k$ is lca}] &amp;= \frac{\left(2^k-1\right)^2 - 2\left(2^{k-1}-1\right)^2}{\left(2^h - 1\right)^2} \\
&amp;=\frac{2^{2k-1} - 1}{\left(2^h -1 \right)^2}
\end{align}
once you work it out. (You can check that these probabilities sum to $1$.)

There are $2^{h-k}$ nodes at height $k$. So the probability that the lca is at height $k$ is $\frac{2^{h+k-1} - 2^{h-k}}{\left(2^h - 1\right)^2}$.

The expected height is thus
\begin{align}
  &amp;\sum_{k=1}^h (k)\frac{2^{h+k-1} - 2^{h-k}}{\left(2^h - 1\right)^2} \\
  &amp;\approx \sum_{k=1}^h \frac{(k)\left(2^{k-1} - 2^{-k}\right)}{2^h} \\
  &amp;\approx h - 1 - \Theta\left(\frac{1}{2^h}\right) .
\end{align}
Simulations bear this out up to three decimal points anyway. By the way, this is very easy to simulate: Suppose the nodes are numbered $1,2,\dots, 2^h - 1$. Pick two random numbers from this range. Now each node $x$'s parent is $\lfloor \frac{x}{2} \rfloor$. To find the lca of two numbers, continue halving (and rounding down) the larger number until they are equal. To find the height of a number, continue halving (and rounding down) until it is one and count the steps. So if your random number generator is comfortable giving you random numbers in the range $[1,2^{100}]$ (as python's seems to be) then you can simulate easily.