两个字符串之间的Levenshtein 或编辑距离是将一个字符串转换为另一个字符串所需的最小编辑次数（添加字母、删除字母或更改字母）。
假设我们有两个字符串，每个大小为个字母的字母表中均匀绘制的字母组成。他们的 Levenshtein 距离的（可能是近似的）分布是什么？
这可以看作是一个极值问题，因为 Levenshtein 距离是对齐两个序列的所有可能方式中的最小错配数。个插入和个缺失的那些中随机选择的比对，错配的数量具有参数为和的二项式分布，因此很容易计算所有这些二项式变量的最小值的分布（如在这个问题中），但在这种情况下，二项式变量不是 IID。
这个问题的解决方案将在生物学中有用（在），因为它会给出不相关序列之间比对的统计特性。
我想这不是一个直接的答案，但您可以尝试模拟场景并检查经验分布以有一个粗略的想法（下面的 R 代码）。
因此，对于长度超过 ~ 100 的字符串，分布似乎是对称的，并且非常窄，大约是字符串长度的 0.53 倍。
# dependencies
library(ggplot2); theme_set(theme_classic())
library(parallel)
library(RecordLinkage)
# settings
alphabet <- c("A", "C", "G", "T")
Nsim <- 1e3
read_lengths <- seq(60, 500, 20)
# function to create a random string of length "n" using letters of the alphabet "alph"
random_read <- function(n, alph=alphabet) paste(sample(alph, size=n, replace=T), collapse="")
# simulate
res <- mclapply(read_lengths,
function(N) replicate(Nsim, levenshteinDist(random_read(N), random_read(N))),
mc.cores=6)
# arrange results as data.frame
res_df <- data.frame(dist=unlist(res),
length=rep(read_lengths, sapply(res, length)))
# plot densities
ggplot(res_df,
aes(x=dist / length, col=length, group=length)) +
geom_density() +
ggtitle("Distribution of Levenshtein distance / length")
ggplot(res_df,
aes(x=length, y=dist / length, col=length)) +
geom_violin(aes(group=length)) +
geom_smooth(col="black", lwd=1) +
ggtitle("Distribution of Levenshtein distance / length")
这看起来有点像 Tracy-Widom 分布？对于最长的公共子序列，有一个“著名”结果将随机字符串之间的 LCS 分布（在一系列限制性假设下）与 Tracy-Widom 分布联系起来：https ://arxiv.org/abs/q-bio/0410012 。https://www.quantamagazine.org/beyond-the-bell-curve-a-new-universal-law-20141015/