An Erdős-Rényi law with shifts
type: Item
instance of: scholarly article
title: An Erdős-Rényi law with shifts
zbMATH Open document ID: 0586.60031
DOI: 10.1016/0001-8708(85)90003-9
author: Richard Arratia
author: Michael S. Waterman
published in: Advances in Mathematics
publication date: 1985-01-01T00:00:00Z
review text: Consider two sequences of ''letters'' \(X_ 1,X_ 2,...\); \(Y_ 1,Y_ 2,..\)., where all the random variables are assumed to be independent and identically distributed. Motivated by the comparison of DNA sequences, the authors are interested in the length of the longest matching consecutive subsequence of \(X_ 1,...,X_ n\) and \(Y_ 1,...,Y_ n\), respectively, i.e. \(M_ n=\max \{m:X_{i+k}=Y_{j+k}\) for \(k=1,...,m\), for some \(0\leq i,j\leq n-m\}\), \(R_ n=\max \{m:X_{i+k}=Y_{i+k}\) for \(k=1,...,m\), for some \(0\leq i\leq n-m\}\), allowing ''shifts'' in the first case and no shifts else. From the Erdős-Rényi law of large numbers for runs in coin tosses, it can be derived that P(\(\lim_{n\to \infty}R_ n/\log_{1/p} n=1)=1\), where \(p=P(X_ 1=Y_ 1)\in (0,1)\). For matching with shifts, the authors analogously prove that P(\(\lim_{n\to \infty}M_ n/\log_{1/p} n=2)\), together with certain convergence rate statements. The case of Markov chains is also treated. The paper above of Darling and Waterman, deals with sequences of letters indexed by points of the integer lattice \({\mathbb{Z}}^ d\). Analogues of the above mentioned limit theorems (without rates) are established for the volume of the largest matching cubes and rectangles in \(\{1,...,n\}^ d\), with and without shifts. Certain algorithms for finding largest squares and rectangles in the case \(d=2\) are also discussed.
Mathematics Subject Classification ID: 60F15
Mathematics Subject Classification ID: 60J10
Mathematics Subject Classification ID: 92D10
zbMATH DE Number: 3940316
zbMATH Keywords: Erdős-Rényi law with shifts
zbMATH Keywords: matching consecutive subsequences
zbMATH Keywords: matching cubes and rectangles
zbMATH Keywords: comparison of DNA sequences
zbMATH Keywords: Erdős- Rényi law of large numbers
zbMATH Keywords: convergence rate
reviewed by: J. G. Steinebach
MaRDI profile type: Publication
full work available at URL: 0001-8708(85)90003-9
OpenAlex ID: W1967191258
Wikidata QID: Q104671667
cites work: Q5732135
cites work: Longest common subsequences of two random sequences
cites work: Q4136276
cites work: Long repetitive patterns in random sequences
cites work: Q4758141
cites work: New approaches for computer analysis of nucleic acid sequences.
cites work: Q5606305
cites work: Q3854367
description: scientific article; zbMATH DE number 3940316