Abstract
where 
is a compact subset of a finite dimensional
Euclidean space, 
, the
function k is a continuous kernel on 
,
and 
is a measure on (typically Lesbesgue measure).
Functional equations of this sort arise from nonlinear rational
expectations models and from the infinite-dimensional analog of
the Howard (1961) ``policy iteration'' algorithm. The randomized
method we propose involves making N IID draws
from a
probability measure 
and
computing an approximate solution 
to the approximate random
Fredholm integral equation:
One way to compute an approximate solution to (2) is to solve
as an 
vector solution to the linear system
where 
is an 
random matrix with (i,j)
element 
. Using
the idea of the ``Nystrom extension'' discussed by Tauchen and
Hussey, we show that can also be viewed as
a random linear operator, an unbiased estimate of the deterministic integral
operator K given by
Appealing to a maximal inequality of Pollard (1989) and a result of
Rust (1996) on the use of randomization as a way to break the curse
of dimensionality of dynamic programming problems, we show that
if 
, then there are several algorithms which succeed in
breaking the curse of dimensionality involved in finding an
-approximation to v in equation (1).
On the other hand by appealing to a result of Werschulz (1991)
one can show that deterministic method for
approximating the solution to (1) (including
the Tauchen and Hussey procedure --
which uses deterministic quadrature methods to approximate
the integral operator K) is subject to an inherent curse of
dimensionality, i.e. the amount of computer tie required to
compute an -approximation to v in equation (1) increases at
rate 
, where d is the dimension of the
domain . The paper concludes with a conjecture that
contrary to a result of Werschulz, randomization does indeed
break the curse of dimensionality even in
the case where 
.