Sublinear algorithms for testing monotone and unimodal distributions

ABSTRACT

The complexity of testing properties of monotone and unimodal distributions, when given access only to samples of the distribution, is investigated. Two kinds of sublinear-time algorithms---those for testing monotonicity and those that take advantage of monotonicity---are provided. The first algorithm tests if a given distribution on [n] is monotone or far away from any monotone distribution in L1-norm; this algorithm uses O(√n) samples and is shown to be nearly optimal. The next algorithm, given a joint distribution on [n] x [n], tests if it is monotone or is far away from any monotone distribution in L1-norm; this algorithm uses O(n^3/2) samples. The problems of testing if two monotone distributions are close in L1-norm and if two random variables with a monotone joint distribution are close to being independent in L1-norm are also considered. Algorithms for these problems that use only poly(log n) samples are presented. The closeness and independence testing algorithms for monotone distributions are significantly more efficient than the corresponding algorithms as well as the lower bounds for arbitrary distributions. Some of the above results are also extended to unimodal distributions.

REFERENCES

• 1: Tuǧkan Batu , Sanjoy Dasgupta , Ravi Kumar , Ronitt Rubinfeld, The complexity of approximating entropy, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510005]
• 2: T. Batu , L. Fortnow , E. Fischer , R. Kumar , R. Rubinfeld , P. White, Testing Random Variables for Independence and Identity, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.442, October 14-17, 2001
• 3: T. Batu , L. Fortnow , R. Rubinfeld , W. D. Smith , P. White, Testing that distributions are close, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.259, November 12-14, 2000
• 4: Tugkan Batu , Ronitt Rubinfeld , Patrick White, Fast Approximate PCPs for Multidimensional Bin-Packing Problems, Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization Problems: Randomization, Approximation, and Combinatorial Algorithms and Techniques, p.245-256, August 08-11, 1999
• 5: Luc Devroye, Algorithms for generating discrete random variables with a given generating function or a given moment sequence, SIAM Journal on Scientific and Statistical Computing, v.12 n.1, p.107-126, Jan. 1991 [doi>10.1137/0912006]
• 6: Yevgeniy Dodis , Oded Goldreich , Eric Lehman , Sofya Raskhodnikova , Dana Ron , Alex Samorodnitsky, Improved Testing Algorithms for Monotonicity, Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization Problems: Randomization, Approximation, and Combinatorial Algorithms and Techniques, p.97-108, August 08-11, 1999
• 7: Funda Ergün , Sampath Kannan , S. Ravi Kumar , Ronitt Rubinfeld , Mahesh Viswanathan, Spot-checkers, Journal of Computer and System Sciences, v.60 n.3, p.717-751, June 2000 [doi>10.1006/jcss.1999.1692]
• 8: Eldar Fischer , Eric Lehman , Ilan Newman , Sofya Raskhodnikova , Ronitt Rubinfeld , Alex Samorodnitsky, Monotonicity testing over general poset domains, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509977]
• 9: O. Goldreich and D. Ron. On testing expansion in bounded degree graphs. Electronic Colloquium on Computational Complexity, TR00-020, 2000.
• 10: O. Goldreich, S. Goldwasser, E. Lehman, D. Ron, and A. Samorodnitsky. Testing monotonicity. Combinatorica, 20(3):301--337, 2000.
• 11: N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, v.4 n.4, p.373-395, Dec. 1984 [doi>10.1007/BF02579150]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

General Terms:
Algorithms, Theory

Keywords:
distribution testing, monotone and unimodal distributions, property testing, sublinear algorithms