Billard method

for random covering

The Billard method was originally used to obtain a necessary condition for almost surely covering the circle $ T $ by random intervals of given lengths $ l _ {1} ,l _ {2} , \dots $( see Dvoretzky problem). Surprisingly, this necessary condition also turned out to be sufficient, not only in this case, but also in many extensions of the Dvoretzky problem. Unaware of this fact, P. Billard chose to give a weaker and more manageable condition, namely [a1]:

$$ \tag{a1 } \sum _ {n = 1 } ^ \infty l _ {n} ^ {2} { \mathop{\rm exp} } ( l _ {1} + \dots + l _ {n} ) = \infty, $$

while the necessary and sufficient condition, stated by L. Shepp in 1972 is [a3]:

$$ \tag{a2 } \sum _ {n = 1 } ^ \infty { \frac{1}{n ^ {2} } } { \mathop{\rm exp} } ( l _ {1} + \dots + l _ {n} ) = \infty $$

when $ 1 > l _ {1} \geq l _ {2} \geq \dots > 0 $( see Dvoretzky problem). Conditions (a1) and (a2) are quite close, but different; (a2) implies (a1), but (a1) does not imply (a2). Both are of interest when trying to cover the $ d $- dimensional torus $ T ^ {d} $ almost surely by random translates of given convex sets $ g _ {n} $ with volumes $ v _ {n} = l _ {n} $( $ n = 1,2, \dots $). In that case, whatever $ d $ may be, (a1) is necessary and (a2) is sufficient. The necessary and sufficient condition lies in between; it is (a2) when $ d = 1 $ and changes, tending to (a1), as $ d $ increases to infinity, at least if one restricts to homothetic simplices [a2].

The general setting for Billard's method is as follows: $ X $ is a space, e.g., $ T $, $ T ^ {d} $, $ \mathbf R $, or $ \mathbf R ^ {d} $; $ ( \Omega, {\mathcal A}, {\mathsf P} ) $ is a probability space; the $ G _ {n} = G _ {n} ( \omega ) $( $ n = 1,2, \dots $; $ \omega \in \Omega $) are random independent subsets of $ X $; and $ K $ is a fixed subset of $ X $. One writes $ G _ {n} ( \omega,x ) = 1 $ if $ x \in G _ {n} $ and $ G _ {n} ( \omega,x ) = 0 $ otherwise. The problem of covering $ K $ almost surely in such a way that each point belongs to infinitely many $ G _ {n} $ reduces to verifying that the series

$$ \sum _ {n = 1 } ^ \infty G _ {n} ( \omega,x ) $$

diverges almost surely on $ K $. Billard's method is to consider the infinite product

$$ \prod _ {n = 1 } ^ \infty { \frac{1 - G _ {n} ( \omega,x ) }{1 - {\mathsf E} G _ {n} ( \omega,x ) } } , $$

where $ {\mathsf E} ( \cdot ) $ denotes mathematical expectation. If $ K $ carries a probability measure $ \sigma $ such that the martingale

$$ S _ {N} = \int\limits {\prod _ {n = 1 } ^ { N } { \frac{1 - G _ {n} ( \omega,x ) }{1 - {\mathsf E} G _ {n} ( \omega,x ) } } } {\sigma ( dx ) } $$

converges in $ L _ {2} ( \Omega ) $, then the infinite product cannot vanish on $ K $ almost surely, and then finite covering cannot take place. This happens whenever $ {\mathsf E} ( S _ {N} ^ {2} ) = O ( 1 ) $, that is, when

$$ {\int\limits \int\limits } {k _ {N} ( x,y ) } {\sigma ( dx ) \sigma ( dy ) } < \infty, $$

where

$$ k _ {N} ( x,y ) = $$

$$ = \prod _ {n = 1 } ^ { N } { \frac{1 - {\mathsf E} G _ {n} ( \omega,x ) - {\mathsf E} G _ {n} ( \omega,y ) + {\mathsf E} G _ {n} ( \omega,x ) {\mathsf E} G _ {n} ( \omega,y ) }{( 1 - {\mathsf E} G _ {n} ( \omega,x ) ) ( 1 - {\mathsf E} G _ {n} ( \omega,y ) ) } } . $$

Therefore, $ K $ is not covered by infinitely many $ G _ {n} $ whenever $ K $ carries a probability measure of bounded energy with respect to the kernels $ k _ {N} ( x,y ) $.

In all cases of interest, this means that $ K $ has a strictly positive capacity with respect to a kernel $ k ( x,y ) $( $ = k _ \infty ( x,y ) $). In the general setting, this is not a necessary and sufficient condition. However, it proves necessary and sufficient in the following cases:

1) $ X = K = T $ and $ G _ {n} = ( 0,l _ {n} ) + \omega _ {n} $, with $ \omega _ {n} $ independent and Lebesgue-distributed on $ T $( the original Dvoretzky problem; here $ k ( x,y ) = k _ {0} ( x,y ) $ and the condition reads $ k _ {0} \notin L _ {1} ( T ) $);

2) $ X = T $, $ K $ is a compact subset of $ X $ and $ G _ {n} $ as above;

3) $ X = K = T ^ {d} $ and $ G _ {n} = g _ {n} + \omega _ {n} $, where the $ g _ {n} $ are homothetic simplices and the $ \omega _ {n} $ are independent and Lebesgue-distributed on $ T ^ {d} $.

The Billard method gives a rough idea of the relation between random coverings and potential theory. To go further, more powerful methods are needed [a2] (see Fitzsimmons–Fristedt–Shepp theorem).

For additional references, see Dvoretzky problem.

References

[a1]	P. Billard, "Séries de Fourier aléatoirement bornées, continues, uniformément convergentes" Ann. Sci. Ecole Norm. Sup. , 82 (1965) pp. 131–179
[a2]	J.-P. Kahane, "Recouvrements aléatoires et théorie du potentiel" Coll. Math. , 60/1 (1990) pp. 387–411
[a3]	L.A. Shepp, "Covering the circle with random arcs" Israel J. Math. , 11 (1972) pp. 328–345