Suppose $X$ and $Y$ are randomly chosen from binary strings of length $n$ with uniform distribution. What is the expected Levenshtein distance between them?
All I currently know is, that it does not exceed the expected Hamming distance which is $\frac{n}{2}$.
If the exact formula is too complicated, I would like to see the asymptotic for $n \to \infty$.