Increasing and other subsequence problems for random interval sequences

Arslan İ., Işlak Ü.

Statistics and Probability Letters, cilt.232, 2026 (SCI-Expanded, Scopus) identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 232
  • Basım Tarihi: 2026
  • Doi Numarası: 10.1016/j.spl.2026.110638
  • Dergi Adı: Statistics and Probability Letters
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, MathSciNet, zbMATH
  • Anahtar Kelimeler: Increasing subsequences, Random intervals, Relations, Subsequence problems, Time series
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

Various relations for comparison of intervals of real numbers are introduced, and the expected length of the corresponding longest increasing subsequence is analyzed. When intervals are randomly generated by taking the minimum and maximum of two independent uniform random variables, we prove that the expected length of the longest increasing subsequence grows on the order of n3. We also investigate the asymptotic behavior of the expected length under alternative comparison relations and random interval models. Discussions on other subsequence problems for interval sequences are included.