The edit or [Levenshtein](http://en.wikipedia.org/wiki/Levenshtein_distance) distance between two strings is the minimum number of single symbol insertions, deletions and substitutions to transform one string into another. For example $$\operatorname{E}(01010,00100)=2.$$


Let $E\_n$ be a random variable giving the edit distance between two random binary strings of length $n$. 



> 
> What bounds can be found for
> 
> 
> $$\lim\_{n \to \infty} \frac{\mathbb{E}(E\_n)}{n} = c\;?$$
> 
> 
> 


According to my non-extensive simulations, $c \approx 0.288$.


There is related work by [Luecker](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.93.4647&rep=rep1&type=pdf) on the expected length of the longest common subsequence which has lower and upper bounds of $0.788071n$ and $0.826280n$. This was a line of work originally started by [Chvatal and Sankoff](ftp://reports.stanford.edu/pub/cstr/reports/cs/tr/75/477/CS-TR-75-477.pdf). However the longest common subsequence length and $n$ minus the edit distance need not be similar.



Expected edit distance
The only rigorous bound I am aware of is due to Gonzalo Navarro\*


$$c\geq 1-{\rm e}/\sqrt{\sigma},$$


for an alphabet of $\sigma$ characters. Obviously, for the binary string ($\sigma=2$) this bound is ineffective. Navarro also mentions a large-$\sigma$ conjecture $c=1-1/\sqrt{\sigma}$, which for the binary string would give $c=0.2929$, quite close to your numerical finding.


\*G. Navarro, [A guided tour to approximate string matching](http://www.eecs.ucf.edu/~dcm/Teaching/COT4810-Spring2011/Literature/ApproximativeStringMatching.pdf) (2001)


