%AAlaikbarpour, Maryam%AGouleakis, Themis%APeebles, John%ARubinfeld, Ronitt%AYodpinyanee, Anak%D2019%I
%K
%MOSTI ID: 10108381
%PMedium: X
%TTowards Testing Monotonicity of Distributions Over General Posets
%XIn this work, we consider the sample complexity required for testing the monotonicity of distributions over partial orders. A distribution p over a poset is {\em monotone} if, for any pair of domain elements x and y such that x⪯y, p(x)≤p(y). To understand the sample complexity of this problem, we introduce a new property called \emph{bigness} over a finite domain, where the distribution is T-big if the minimum probability for any domain element is at least T. We establish a lower bound of Ω(n/logn) for testing bigness of distributions on domains of size n. We then build on these lower bounds to give Ω(n/logn) lower bounds for testing monotonicity over a matching poset of size n and significantly improved lower bounds over the hypercube poset. We give sublinear sample complexity bounds for testing bigness and for testing monotonicity over the matching poset. We then give a number of tools for analyzing upper bounds on the sample complexity of the monotonicity testing problem.
Country unknown/Code not availableOSTI-MSA