  We present exponential error estimates and demonstrate an algebraic
convergence rate for the homogenization of level-set convex Hamilton-Jacobi
equations in i.i.d. random environments, the first quantitative homogenization
results for these equations in the stochastic setting. By taking advantage of a
connection between the metric approach to homogenization and the theory of
first-passage percolation, we obtain estimates on the fluctuations of the
solutions to the approximate cell problem in the ballistic regime (away from
flat spot of the effective Hamiltonian). In the sub-ballistic regime (on the
flat spot), we show that the fluctuations are governed by an entirely different
mechanism and the homogenization may proceed, without further assumptions, at
an arbitrarily slow rate. We identify a necessary and sufficient condition on
the law of the Hamiltonian for an algebraic rate of convergence to hold in the
sub-ballistic regime and show, under this hypothesis, that the two rates may be
merged to yield comprehensive error estimates and an algebraic rate of
convergence for homogenization.
  Our methods are novel and quite different from the techniques employed in the
periodic setting, although we benefit from previous works in both first-passage
percolation and homogenization. The link between the rate of homogenization and
the flat spot of the effective Hamiltonian, which is related to the
nonexistence of correctors, is a purely random phenomenon observed here for the
first time.
