The Erdős-Rényi law in distribution, for coin tossing and sequence matching

DOI10.1214/aos/1176347615zbMath0712.92016OpenAlexW2036306946MaRDI QIDQ749471

Richard Arratia, Louis Gordon, Michael S. Waterman

Publication date: 1990

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

Full work available at URL: https://doi.org/10.1214/aos/1176347615

zbMATH Keywords

approximationsmolecular biologyscan statisticsmoving averagesequence matchinganalysis of DNA sequencesChen-Stein method of Poisson approximationcoin tossesdistribution of counts of matchesErdős-Rényi law in distributionhead-runsindependent sequences of independent, identically distributed letters from finite alphabetstotal variation distances

Mathematics Subject Classification ID

Combinatorial probability (60C05) Large deviations (60F10) Protein sequences, DNA sequences (92D20) Approximations to statistical distributions (nonasymptotic) (62E17) Limit theorems in probability theory (60F99)

Related Items (39)

A comparison of scores of two protein structures with foldings ⋮ Compound Poisson approximation: A user's guide ⋮ Hausdorff dimension of the maximal run-length in dyadic expansion ⋮ Understanding nonsense correlation between (independent) random walks in finite samples ⋮ Exact probability of fixed patterns occurring in a random sequence ⋮ Poisson approximations for 2-dimensional patterns ⋮ Pattern matching between two non-aligned random sequences ⋮ Combinational optimization problems for which almost every algorithm is asymptotically optimal ⋮ Approximations for a three dimensional scan statistic ⋮ Long strange segments, ruin probabilities and the effect of memory on moving average processes ⋮ One dimensional scan statistics generated by some dependent stationary sequences ⋮ A note on the run length function for intermittent maps ⋮ The time of bootstrap percolation with dense initial sets ⋮ A Probabilistic Analysis of a String Editing Problem and its Variations ⋮ Getting the Lay of the Land in Discrete Space: A Survey of Metric Dimension and Its Applications ⋮ Fundamentals of Stein's method ⋮ Probabilistic Divide-and-Conquer: A New Exact Simulation Method, With Integer Partitions as an Example ⋮ Searching a bitstream in linear time for the longest substring of any given density ⋮ On the tail probability of the longest well-matching run. ⋮ Periodically driven jump processes conditioned on large deviations ⋮ Large deviations-based upper bounds on the expected relative length of longest common subsequences ⋮ Longest runs in a sequence of \(m\)-dependent random variables ⋮ A phase transition for the minimum free energy of secondary structures of a random RNA ⋮ A Strong Law for the Rate of Growth of Long Latency Periods in a Cloud Computing Service ⋮ A local algorithm for DNA sequence alignment with inversions ⋮ Poisson, compound Poisson and process approximations for testing statistical significance in sequence comparisons ⋮ Anomalous time-scaling of extreme events in infinite systems and Birkhoff sums of infinite observables ⋮ Asymptotics for local maximal stack scores with general loop penalty function ⋮ A generalization of the Erdős-Rényi limit theorem and the corresponding multifractal analysis ⋮ An improved approximation for assessing the statistical significance of molecular sequence features ⋮ EXCEPTIONAL SETS RELATED TO THE RUN-LENGTH FUNCTION OF BETA-EXPANSIONS ⋮ Testing Stream Ciphers by Finding the Longest Substring of a Given Density ⋮ A Phase Transition for the Distribution of Matching Blocks ⋮ Optimal data compression algorithm ⋮ Universal Data Compression Algorithm Based on Approximate String Matching ⋮ Poisson approximation ⋮ Moment estimates in the first Borel-Cantelli lemma with applications to mean deviation frequencies ⋮ Matching of observations of dynamical systems, with applications to sequence matching ⋮ Approximate \(p\)-values for local sequence alignments.

This page was built for publication: The Erdős-Rényi law in distribution, for coin tossing and sequence matching