Distancia de edición prevista

Question

La edición o Levenshtein La distancia entre dos cadenas es el número mínimo de inserciones, supresiones y sustituciones de un solo símbolo para transformar una cadena en otra. Por ejemplo $$\operatorname{E}(01010,00100)=2.$$

Dejemos que $E_n$ sea una variable aleatoria que da la distancia de edición entre dos cadenas binarias aleatorias de longitud $n$ .

Qué límites se pueden encontrar para

$$\lim_{n \to \infty} \frac{\mathbb{E}(E_n)}{n} = c\;?$$

Según mis simulaciones no exhaustivas, $c \approx 0.288$ .

Existe un trabajo relacionado de Luecker sobre la longitud esperada de la subsecuencia común más larga que tiene límites inferiores y superiores de $0.788071n$ y $0.826280n$ . Esta fue una línea de trabajo iniciada originalmente por Chvatal y Sankoff . Sin embargo, la longitud de la subsecuencia común más larga y $n$ menos la distancia de edición no tienen por qué ser similares.

Answer 1

Sin embargo, no estoy seguro de que haya ningún límite inferior probado hasta ahora.

Esto debería ser un comentario, pero es demasiado largo.

Depende mucho de la calidad del límite inferior que quieras. La más trivial se puede obtener simplemente diciendo que si tenemos $k$ supresiones, $k$ inserciones, y $m$ sustituciones, podemos obtener sólo ${n\choose k}^2{n-k\choose m}$ nuevas secuencias a partir de una determinada. Ahora bien, si eso es mucho menos que $2^n$ por cada $k,m$ con $2k+m < cn$ entonces el límite es al menos $c$ . Utilizando la aproximación simple $m!\approx m^me^{-m}$ vemos que todo lo que necesitamos es asegurar que $$ 2\mu\log\mu+(1-\mu)\log(1-\mu)+\nu\log\nu+(1-\mu-\nu)\log(1-\mu-\nu)>-\log 2 $$ siempre que $2\mu+\nu\le c$ que (tras algunos cálculos) da como resultado $c>0.18$ . Por supuesto, esto es muy burdo porque no tiene en cuenta el hecho de que el número de formas de convertir una secuencia en otra dentro de la distancia de edición es típicamente exponencial en $n$ también.

Answer 2

Hice algunas simulaciones yo mismo, (5000 de cada longitud de cadena 1-1000) y pensé en compartirlas aquí. Se han comparado con el límite conjeturado por Carlo de $1-1/\sqrt{2}$ (en azul).

Para mí, la conjetura parece bastante probable, ya que la distancia media más pequeña que obtengo es de 0,296 en $n=1000$ .