Expected Density of Random Minimizers

Minimizer schemes, or just minimizers, are a very important computational primitive in sampling and sketching biological strings. Assuming a fixed alphabet of size σ, a minimizer is defined by two integers k,w≥2 and a total order ρ on strings of length k (also called k-mers). A string is processed by a sliding window algorithm that chooses, in each window of length w+k-1, its minimal k-mer with respect to ρ. A key characteristic of the minimizer is the expected density of chosen k-mers among all k-mers in a random infinite σ-ary string. Random minimizers, in which the order ρ is chosen uniformly at random, are often used in applications. However, little is known about their expected density DR_σ(k,w) besides the fact that it is close to 2w+1 unless w≫k.    We first show that DR_σ(k,w) can be computed in O(kσ^k+w) time. Then we attend to the case w≤k and present a formula that allows one to compute DR_σ(k,w) in just O(wlogw) time. Further, we describe the behaviour of DR_σ(k,w) in this case, establishing the connection between DR_σ(k,w), DR_σ(k+1,w), and DR_σ(k,w+1). In particular, we show that DR_σ(k,w)<2w+1 (by a tiny margin) unless w is small. We conclude with some partial results and conjectures for the case w>k.