Econometrica: Jul 2022, Volume 90, Issue 4

A Comment on “Using Randomization to Break the Curse of Dimensionality”
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.

Log In To View Full Content Original Article

Supplemental Material

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

Read More View PDF