On the Order of the Central Moments of the Length of the Longest Common Subsequences in Random Words

DOI10.1007/978-3-319-40519-3_5zbMath1382.60020arXiv1212.3265OpenAlexW2336450993MaRDI QIDQ2954041

Jinyong Ma, Christian Houdré

Publication date: 11 January 2017

Published in: High Dimensional Probability VII (Search for Journal in Brave)

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

zbMATH Keywords

longest common subsequenceEfron-Stein inequalitylast passage percolationBurkholder inequality\(r\)-th central moment

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Combinatorial probability (60C05)

Related Items (4)

On the variance of the optimal alignments score for binary random words and an asymmetric scoring function ⋮ Normal Approximation for Functions of Hidden Markov Models ⋮ Lower bounds for fluctuations in first-passage percolation for general distributions ⋮ A general method for lower bounds on fluctuations of random variables

Cites Work

• On the variance of the optimal alignments score for binary random words and an asymmetric scoring function
• On the longest common increasing binary subsequence
• Martingale inequalities and the jackknife estimate of variance
• An Efron-Stein inequality for nonsymmetric statistics
• The rate of convergence of the mean length of the longest common subsequence
• Sparse long blocks and the micro-structure of the longuest common subsequences
• Standard deviation of the longest common subsequence
• Sharp Martingale and Semimartingale Inequalities
• Longest common subsequences of two random sequences

This page was built for publication: On the Order of the Central Moments of the Length of the Longest Common Subsequences in Random Words