The Erdős-Rényi strong law for pattern matching with a given proportion of mismatches

DOI10.1214/aop/1176991262zbMath0688.62019OpenAlexW2147580512WikidataQ104764075 ScholiaQ104764075MaRDI QIDQ1263898

Michael S. Waterman, Richard Arratia

Publication date: 1989

Published in: The Annals of Probability (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1214/aop/1176991262

zbMATH Keywords

Markov chainsIsing modelHamming distanceDNA sequencesprotein sequencesPotts modelmultidimensional arraysErdős-Rényi law for coin tossinglength of the longest contiguous matchingstrong law for matching

Mathematics Subject Classification ID

Asymptotic distribution theory in statistics (62E20) Applications of statistics to biology and medical sciences; meta analysis (62P10) Strong limit theorems (60F15)

Related Items (17)

Erdős-Rényi laws for Gibbs measures ⋮ String matching bounds via coding ⋮ Duality between the local score of one sequence and constrained hidden Markov model ⋮ The Hausdorff dimension of level sets described by Erdős-Rényi average ⋮ A Probabilistic Analysis of a String Editing Problem and its Variations ⋮ On the shortest distance between orbits and the longest common substring problem ⋮ Dictionary-symbolwise flexible parsing ⋮ Languages with mismatches ⋮ Large deviations-based upper bounds on the expected relative length of longest common subsequences ⋮ Poisson, compound Poisson and process approximations for testing statistical significance in sequence comparisons ⋮ Adaptive multiscale detection of filamentary structures in a background of uniform random points ⋮ A generalization of the Erdős-Rényi limit theorem and the corresponding multifractal analysis ⋮ Non-parametric change-point estimation using string matching algorithms ⋮ Testing Stream Ciphers by Finding the Longest Substring of a Given Density ⋮ Optimal data compression algorithm ⋮ Universal Data Compression Algorithm Based on Approximate String Matching ⋮ Longest common substring for random subshifts of finite type

This page was built for publication: The Erdős-Rényi strong law for pattern matching with a given proportion of mismatches