A central limit theorem for the length of the longest common subsequences in random words

DOI10.1214/22-EJP894WikidataQ122202419 ScholiaQ122202419MaRDI QIDQ2679696

Christian Houdré, Ümit Işlak

Publication date: 23 January 2023

Published in: Electronic Journal of Probability (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1408.1559

zbMATH Keywords

Stein's methodcentral limit theoremTracy-Widom distributionlast passage percolationlongest common subsequencesoptimal alignmentsrandom permutationsUlam's problemrandom wordssupersequencesedit/Levenshtein distance

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Combinatorics on words (68R15) Permutations, words, matrices (05A05) Combinatorial probability (60C05) Large deviations (60F10)

Related Items (3)

On the variance of the optimal alignments score for binary random words and an asymmetric scoring function ⋮ Limit theorems for longest monotone subsequences in random Mallows permutations ⋮ A general method for lower bounds on fluctuations of random variables

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Closeness to the diagonal for longest common subsequences in random words
• On the variance of the optimal alignments score for binary random words and an asymmetric scoring function
• Fundamentals of Stein's method
• On the limiting law of the length of the longest common and increasing subsequences in random words
• On the longest common increasing binary subsequence
• A new method of normal approximation
• An Efron-Stein inequality for nonsymmetric statistics
• A variational problem for random Young tableaux
• The rate of convergence of the mean length of the longest common subsequence
• A note on the expected length of the longest common subsequences of two i.i.d. random permutations
• New Berry-Esseen bounds for functionals of binomial point processes
• On rates of convergence for common subsequences and first passage time
• On the limiting law of the length of the longest common and increasing subsequences in random words with arbitrary distribution
• Lower bounds for fluctuations in first-passage percolation for general distributions
• Standard deviation of the longest common subsequence
• Minimal spanning trees and Stein's method
• Expected length of the longest common subsequence for large alphabets
• Normal Approximation by Stein’s Method
• Longest common subsequences of two random sequences
• Common Subsequences and Supersequences and their Expected Length
• On the distribution of the length of the longest increasing subsequence of random permutations
• Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem
• On Stein's Method for Infinitely Divisible Laws with Finite First Moment
• Normal Approximation for Functions of Hidden Markov Models
• On the rate of convergence for the length of the longest common subsequences in hidden Markov models

This page was built for publication: A central limit theorem for the length of the longest common subsequences in random words