In this work, we study the problem of testing subsequence-freeness. For a given subsequence (word) w = w1 … wk, a sequence (text) T = t1 … tn is said to contain w if there exist indices 1 ≤ i1 < ⃛ < ik ≤ n such that for every 1 ≤ j ≤ k. Otherwise, T is w-free. While a large majority of the research in property testing deals with algorithms that perform queries, here we consider sample-based testing (with one-sided error). In the “standard” sample-based model (i.e., under the uniform distribution), the algorithm is given samples (i, ti) where i is distributed uniformly independently at random. The algorithm should distinguish between the case that T is w-free, and the case that T is ∊-far from being w-free (i.e., more than an ∊-fraction of its symbols should be modified so as to make it w-free). Freitag, Price, and Swartworth (Proceedings of RANDOM, 2017) showed that O(k2 log k/∊) samples suffice for this testing task. We obtain the following results. The number of samples sufficient for sample-based testing (under the uniform distribution) is O(k/∊). This upper bound builds on a characterization that we present for the distance of a text T from w-freeness in terms of the maximum number of copies of w in T, where these copies should obey certain restrictions. We prove a matching lower bound, which holds for every word w. This implies that the above upper bound is tight. The same upper bound holds in the more general distribution-free sample-based model. In this model the algorithm receives samples (i, ti) where i is distributed according to an arbitrary distribution p (and the distance from w-freeness is measured with respect to p). We highlight the fact that while we require that the testing algorithm work for every distribution and when only provided with samples, the complexity we get matches a known lower bound for a special case of the seemingly easier problem of testing subsequence-freeness under the uniform distribution and with queries (Canonne et al., Theory of Computing, 2019).

For an integer k ≥ 0, a sequence σ = σ₁,… ,σ_n over a fully ordered set is k-modal, if there exist indices 1 = a₀ < a₁ < … < a_{k+1} = n such that for each i, the subsequence σ_{a_i},… ,σ_{a_{i+1}} is either monotonically non-decreasing or monotonically non-increasing. The property of k-modality is a natural extension of monotonicity, which has been studied extensively in the area of property testing. We study one-sided error property testing of k-modality in the distribution-free sample-based model. We prove an upper bound of O({√{kn}log k}/ε) on the sample complexity, and an almost matching lower bound of Ω(√{kn}/ε). When the underlying distribution is uniform, we obtain a completely tight bound of Θ(√{kn/ε}), which generalizes what is known for sample-based testing of monotonicity under the uniform distribution.