Matching strings in encoded sequences

DOI10.3150/19-BEJ1181zbMATH Open1442.94028arXiv1903.09625MaRDI QIDQ2174991FDOQ2174991

Authors: Adriana Coutinho, Rodrigo Lambert, Jérôme Rousseau 

Publication date: 27 April 2020

Published in: Bernoulli (Search for Journal in Brave)

Abstract: We investigate the longest common substring problem for encoded sequences and its asymptotic behaviour. The main result is a strong law of large numbers for a re-scaled version of this quantity, which presents an explicit relation with the R'enyi entropy of the source. We apply this result to the zero-inflated contamination model and the stochastic scrabble. In the case of dynamical systems, this problem is equivalent to the shortest distance between two observed orbits and its limiting relationship with the correlation dimension of the pushforward measure. An extension to the shortest distance between orbits for random dynamical systems is also provided.

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

Recommendations

• Rényi entropy and pattern matching for run-length encoded sequences
• Longest common substring for random subshifts of finite type
• On the shortest distance between orbits and the longest common substring problem
• Critical phenomena in sequence matching
• Maximal length of common words among random letter sequences

zbMATH Keywords

random dynamical systemscorrelation dimensionstring matchingcodingshortest distanceRényi entropy

Mathematics Subject Classification ID

Measures of information, entropy (94A17) Strong limit theorems (60F15) Entropy and other invariants (28D20) Symbolic dynamics (37B10) Generation, random and stochastic difference and differential equations (37H10)

Cites Work

• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Quantitative recurrence results
• Title not available (Why is that?)
• Entry and return times distribution
• Title not available (Why is that?)
• Laws of rare events for deterministic and random dynamical systems
• Recurrence, dimensions, and Lyapunov exponents.
• Some asymptotic properties of the entropy of a stationary ergodic data source with applications to data compression
• Entropy and data compression schemes
• Information theory and coding by example
• Recurrence rate in rapidly mixing dynamical systems
• Inequalities for the occurrence times of rare events in mixing processes. The state of the art
• Poincaré recurrence for observations
• Exponential decay of correlations for randomly chosen hyperbolic toral automorphisms
• Limit distribution of maximal non-aligned two-sequence segmental score
• AN INTRODUCTION TO QUANTITATIVE POINCARÉ RECURRENCE IN DYNAMICAL SYSTEMS
• Recurrence for random dynamical systems
• More on recurrence and waiting times
• On the spectra of randomly perturbed expanding maps
• Pointwise dimensions for Poincaré recurrences associated with maps and special flows
• Hitting time statistics for observations of dynamical systems
• Return times in a process generated by a typical partition
• Critical phenomena for sequence matching with scoring
• An Erdős-Rényi law with shifts
• Large deviations for short recurrence
• Stochastic scrabble: large deviations for sequences with scores
• Nonparametric entropy estimation for stationary processes and random fields, with applications to English text
• The distribution of the short-return function
• Random perturbations of stochastic processes with unbounded variable length memory
• The Rényi entropy function and the large deviation of short return times
• Stochastically perturbed chains of variable memory
• A suboptimal lossy data compression based on approximate pattern matching
• The asymptotics of waiting times between stationary processes, allowing distortion
• On the shortest distance between orbits and the longest common substring problem
• Rényi Entropies and Large Deviations for the First Match Function
• A Phase Transition for the Distribution of Matching Blocks
• From the divergence between two measures to the shortest path between two observables
• On compound Poisson approximation for sequence matching
• Longest common substring for random subshifts of finite type
• The Shortest Possible Return Time of <inline-formula> <tex-math notation="LaTeX">$\beta$ </tex-math> </inline-formula>-Mixing Processes

Cited In (8)

• Minimal distance between random orbits
• Rényi entropy and pattern matching for run-length encoded sequences
• Shortest distance between multiple orbits and generalized fractal dimensions
• Common substring with shifts in \(b\)-ary expansions
• Matching of observations of dynamical systems, with applications to sequence matching
• Longest common substring for random subshifts of finite type
• Sequence matching with binary codes
• On the shortest distance between orbits and the longest common substring problem

This page was built for publication: Matching strings in encoded sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2174991)