Testing for forbidden order patterns in an array

A sequence f : [ n ] → R contains a pattern π ∈ S k , that is, a permutations of [ k ], iff there are indices i 1  < … <  i k , such that f ( i x ) >  f ( i y ) whenever π ( x ) >  π ( y ). Otherwise, f is π ‐free. We study the property testing problem of distinguishing, for a fixed π , between π ‐free sequences and the sequences which differ from any π ‐free sequence in more than ϵ n places. Our main findings are as follows: (1) For monotone patterns, that is, π  = ( k , k  − 1,…,1) and π  = (1,2,…, k ), there exists a nonadaptive one‐sided error ϵ ‐test of( ϵ − 1 log n ) O ( k 2 )query complexity. For any other π , any nonadaptive one‐sided error test requires Ω ( n ) queries. The latter lower‐bound is tight for π  = (1,3,2). For specific π ∈ S kit can be strengthened to Ω( n 1 − 2/( k  + 1) ). The general case upper‐bound is O ( ϵ −1/ k n 1 − 1/ k ). (2) For adaptive testing the situation is quite different. In particular, for any π ∈ S 3there exists an adaptive ϵ ‐tester of( ϵ − 1 log n ) O ( 1 )query complexity.