Billard method

for random covering

The Billard method was originally used to obtain a necessary condition for almost surely covering the circle by random intervals of given lengths (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]:

(a1)

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

(a2)

when (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 -dimensional torus almost surely by random translates of given convex sets with volumes (). In that case, whatever may be, (a1) is necessary and (a2) is sufficient. The necessary and sufficient condition lies in between; it is (a2) when and changes, tending to (a1), as increases to infinity, at least if one restricts to homothetic simplices [a2].

The general setting for Billard's method is as follows: is a space, e.g., , , , or ; is a probability space; the (; ) are random independent subsets of ; and is a fixed subset of . One writes if and otherwise. The problem of covering almost surely in such a way that each point belongs to infinitely many reduces to verifying that the series

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

where denotes mathematical expectation. If carries a probability measure such that the martingale

converges in , then the infinite product cannot vanish on almost surely, and then finite covering cannot take place. This happens whenever , that is, when

where

Therefore, is not covered by infinitely many whenever carries a probability measure of bounded energy with respect to the kernels .

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

1) and , with independent and Lebesgue-distributed on (the original Dvoretzky problem; here and the condition reads );

2) , is a compact subset of and as above;

3) and , where the are homothetic simplices and the are independent and Lebesgue-distributed on .

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