Sparse covers for sums of indicators

详细信息    查看全文

• 作者：Constantinos Daskalakis ; Christos Papadimitriou
• 关键词：60F99
• 刊名：Probability Theory and Related Fields
• 出版年：2015
• 出版时间：August 2015
• 年：2015
• 卷：162
• 期：3-4
• 页码：679-705
• 全文大小：585 KB
• 参考文献：1.Berry, A.C.: The accuracy of the Gaussian approximation to the sum of independent variates. Trans. Am. Math. Soc. 49(1), 122鈥?36 (1941)View Article
  2.Barbour, A.D., Hall, P.: On the rate of Poisson convergence. Math. Proc. Cambridge Philos. Soc. 95(03), 473鈥?80 (1984)MATH MathSciNet View Article
  3.Barbour, A.D., Holst, L., Janson, S.: Poisson Approximation. Oxford University Press (1992)
  4.Barbour, A.D., Lindvall, T.: Translated Poisson approximation for Markov chains. J. Theor. Prob. 19(3), 609鈥?30 (2006)MATH MathSciNet View Article
  5.Blonski, M.: Anonymous games with binary actions. Games Econ. Behav. 28(2), 171鈥?80 (1999)MATH MathSciNet View Article
  6.Chen, L.H.Y., Goldstein, L., Shao, Q.-M.: Normal approximation by Stein鈥檚 method. Springer (2010)
  7.Chen, L.H.Y.: On the convergence of Poisson binomial to Poisson distributions. Ann. Prob. 2, 178鈥?80 (1974)MATH View Article
  8.Chen, S.X., Liu, J.S.: Statistical applications of the Poisson-binomial and conditional Bernoulli distributions. Stat. Sin. 7, 875鈥?92 (1997)MATH
  9.Daskalakis C.: An efficient PTAS for two-strategy anonymous games. In : the 4th international workshop on internet and network economics (WINE) (2008)
  10.Daskalakis, C., Diakonikolas, I., Servedio R.: Learning Poisson binomial distributions. In the 44th annual ACM symposium on theory of computing (STOC) (2012)
  11.Deheuvels, P., Pfeifer, D.: A semigroup approach to Poisson approximation. Ann. Prob. 14, 663鈥?76 (1986)MATH MathSciNet View Article
  12.Daskalakis, C., Papadimitriou, C.H.: Computing equilibria in anonymous games. In: the 48th annual IEEE symposium on foundations of computer science (FOCS) (2007)
  13.Daskalakis, C., Papadimitriou, C.H.: On oblivious PTAS鈥檚 for Nash equilibrium. In: the 41st annual ACM symposium on theory of computing (STOC) (2009)
  14.Daskalakis, C., Papadimitriou, C.H.: Approximate Nash equilibria in anonymous games. J. Econ. Theory, to appear (2013)
  15.Ehm, W.: Binomial approximation to the Poisson binomial distribution. Stat. Prob. Lett. 11, 7鈥?6 (1991)MATH MathSciNet View Article
  16.Esseen, C.-G.: On the Liapunoff limit of error in the theory of probability. Arkiv f枚r Mate. Astron. och Fysik A28, 1鈥?9 (1942)MathSciNet
  17.Hodges, J.L., Le Cam, L.: The Poisson approximation to the Poisson binomial distribution. Ann. Math. Stat. 31(3), 737鈥?40 (1960)MATH View Article
  18.Le Cam, L.: An approximation theorem for the Poisson binomial distribution. Pac. J. Math. 10, 1181鈥?197 (1960)MATH View Article
  19.Mikhailov, V.G.: On a refinement of the central limit theorem for sums of independent random indicators. Theory Prob. Appl. 38, 479鈥?89 (1993)View Article
  20.Milchtaich, I.: Congestion games with player-specific payoff functions. Games Econ. Behav. 13, 111鈥?24 (1996)MATH MathSciNet View Article
  21.Motwani, R., Raghavan, P.: Randomized algorithms. Cambridge University Press (1995)
  22.Poisson, S.D.: Recherches sur la Probabilit茅 des Jugements en Mati猫re Criminelle et en Mati猫re Civile. Bachelier, Paris (1837)
  23.R枚llin, A.: Translated Poisson approximation using exchangeable pair couplings. Ann. Appl. Prob. 17, 1596鈥?614 (2007)MATH View Article
  24.Roos, B.: Binomial approximation to the Poisson binomial distribution: the Krawtchouk expansion. Theory Prob. Appl. 45(2), 328鈥?44 (2000)
  25.Soon, S.Y.T.: Binomial approximation for dependent indicators. Stat. Sin. 6, 703鈥?14 (1996)MATH MathSciNet
  26.Michael, J.: Steele Le Cam鈥檚 inequality and Poisson approximation. Am. Math. Mon. 101, 48鈥?4 (1994)View Article
  27.Volkova, A.Y.U.: A refinement of the central limit theorem for sums of independent random indicators. Theory Prob. Appl. 40, 791鈥?94 (1995)MathSciNet View Article
  28.Wang, Y.H.: On the number of successes in independent trials. Stat. Sin. 3, 295鈥?12 (1993)MATH
  29.Zolotarev, Vladimir M.: Random symmetric polynomials. J. Math. Sci. 38(5), 2262鈥?272 (1987)MATH MathSciNet View Article
  
• 作者单位：Constantinos Daskalakis (1)
  Christos Papadimitriou (2)
  
  1. EECS and CSAIL, MIT, Cambridge, MA, USA
  2. Computer Science, U.C. Berkeley, Berkeley, CA, USA
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Probability Theory and Stochastic Processes
  Mathematical and Computational Physics
  Quantitative Finance
  Mathematical Biology
  Statistics for Business, Economics, Mathematical Finance and Insurance
  Operation Research and Decision Theory
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1432-2064

文摘

For all \(n, \epsilon >0\), we show that the set of Poisson Binomial distributions on \(n\) variables admits a proper \(\epsilon \)-cover in total variation distance of size \(n^2+n \cdot (1/\epsilon )^{O(\log ^2 (1/\epsilon ))}\), which can also be computed in polynomial time. We discuss the implications of our construction for approximation algorithms and the computation of approximate Nash equilibria in anonymous games.