Quasi-Regular Sequences

MaRDI QIDQ6326196zbMATH OpenFDO

Authors Joshua Frisch, Wade Hann-Caruthers, Pooya Vahidi Ferdowsi

Publication date 29 September 2019

Abstract: Let $Sigma$ be a countable alphabet. For $rgeq1$, an infinite sequence $s$ with characters from $Sigma$ is called $r$-quasi-regular, if for each $sigmainSigma$ the ratio of the longest to shortest interval between consecutive occurrences of $sigma$ in $s$ is bounded by $r$. In this paper, we answer a question asked by Kempe, Schulman, and Tamuz, and prove that for any probability distribution $mathbfp$ on a finite alphabet $Sigma$, there exists a $2$-quasi-regular infinite sequence with characters from $Sigma$ and density of characters equal to $mathbfp$. We also prove that as $leftlVertmathbfpightVer{t}_{i}nfty$ tends to zero, the infimum of $r$ for which $r$-quasi-regular sequences with density $mathbfp$ exist, tends to one. This result has a corollary in the Pinwheel Problem: as the smallest integer in the vector tends to infinity, the density threshold for Pinwheel schedulability tends to one.

This page was built for publication: Quasi-Regular Sequences

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