Stochastic search in a Banach space
This paper establishes a probabilistic result which has implications for the numerical implementation of certain nonparametric statistical procedures. To describe the probabilistic result, let \(\lambda_ n\), \(n\geq 1\), be an increasing sequence of integers, totally arbitrary except for the condition that \(\lambda_ n\uparrow\infty\). Let \(Y_ 1,Y_ 2,\dots\) be i.i.d. random variables with values in an infinite- dimensional Banach space \(B\), and whose common distribution \(\mu\) has as its support the unit ball of \(B\). Then no matter what \(\varepsilon>0\) is selected, and no matter which \(\theta_ 0\) in the unit ball of \(B\) is chosen, and no matter what the rate at which \(\lambda_ n\uparrow\infty\), one clearly has \[ \lim_{n\to\infty}P\{| Y_ i- \theta_ 0|\leq\varepsilon\text{ for some } i\leq\lambda_ n\}=1. \tag{1.1} \] Indeed, if \(\delta_ \varepsilon\equiv P\{| Y_ 1- \theta_ 0|<\varepsilon\}\), then the probability in (1.1) is equal to \(1-[1-\delta_ \varepsilon]^{\lambda_ n}\), which converges to 1 as \(\lambda_ n\uparrow\infty\), since \(\delta_ \varepsilon>0\). On the other hand, we show that if \(\varepsilon\) in (1.1) is allowed to shrink with \(n\), as \(n\to\infty\), a result such as (1.1) cannot possibly hold, no matter how slowly \(\varepsilon\) shrinks with \(n\). More precisely, pick \(\gamma>0\). Then no matter how small \(\gamma\) is, and no matter how fast \(\lambda_ n\uparrow\infty\), there will exist an infinite number of points \(\theta_ 0\) within the unit ball such that \[ \lim_{n\to\infty}P\{| Y_ i-\theta_ 0|\leq n^{- \gamma}\text{ for some } i\leq\lambda_ n\}=0. \tag{1.2} \] The actual result proved in this paper is a stronger almost sure version of (1.2). Statement (1.2) and its stronger version should be compared with (1.1) and its stronger version: for almost every \(w\), the sequence \(Y_ 1(w)\), \(Y_ 2(w),\dots\) is dense in the unit ball of \(B\). There can be no uniform distribution on the unit ball of an infinite- dimensional Banach space; the main result therefore quantifies how this fact is reflected in an i.i.d. sequence. The \(n\)-dependent ``neighborhoods of \(\theta_ 0\) involved in (1.2) are given a formal description as ``\(\gamma\)-funnels, in section 2, where they have a natural statistical interpretation. If \(B\) is assumed finite dimensional, then results like (1.2) are often false, depending on \(\mu\). The result (1.2) was motivated by considerations involving stochastic search for extrema as a means of calculating, approximately, nonparametric goodness of fit tests and maximum likelihood estimators for an infinite dimensional parameter. Such motivations are discussed in section 2. In finite dimensional situations, simple Monte Carlo search for extrema often works, but can be inefficient. One message of the main theorem in section 3 is that, in a Banach space, such methods are not merely inefficient: they fail (for an infinite number of parameter values) to accomplish the desired end. This discouraging fact notwithstanding, it is sometimes still possible to devise an effective stochastic search for extrema. A possible key here is to take the search variables \(Y_ i\) not i.i.d. One such technique -- the ``local stochastic search -- is described in section 4, and applied to a particular nonparametric goodness of fit statistic. For the entire collection see [Zbl 0773.00018].
This page was built for publication: Stochastic search in a Banach space
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3139514)