Econometrica

Journal Of The Econometric Society

An International Society for the Advancement of Economic
Theory in its Relation to Statistics and Mathematics

Edited by: Guido W. Imbens • Print ISSN: 0012-9682 • Online ISSN: 1468-0262

Econometrica: Jul, 2022, Volume 90, Issue 4

A Comment on “Using Randomization to Break the Curse of Dimensionality”

https://doi.org/10.3982/ECTA17664
p. 1915-1929

Robert L. Bray

Rust (1997b) discovered a class of dynamic programs that can be solved in polynomial time with a randomized algorithm. For these dynamic programs, the optimal values of a polynomially large sample of states are sufficient statistics for the (near) optimal values everywhere, and the values of this random sample can be bootstrapped from the sample itself. However, I show that this class is limited, as it requires all but a vanishingly small fraction of state variables to behave arbitrarily similarly to i.i.d. uniform random variables.


Full Content Original Article

Supplemental Material

Supplement to "A Comment on 'Using Randomization to Break the Curse of Dimensionality'"

Bray, Robert L.

Online Appendix