  We study the average edit distance between two random strings. More
precisely, we adapt a technique introduced by Lueker in the context of the
average longest common subsequence of two random strings to improve the known
upper bound on the average edit distance. We improve all the known upper bounds
for small alphabets. We also provide a new implementation of Lueker technique
to improve the lower bound on the average length of the longest common
subsequence of two random strings for all small alphabets of size other than
$2$ and $4$.
