CORMSIS Seminar Event

Coin tossing is a naive, simple, but sometimes powerful method in statistics and the design of randomized algorithms. In a typical application, random sampling based on coin tossing can be applied to estimate an extreme value, say maximum, of a function f over a set S. To do so, one may select a simpler (even finite) subset S0, randomly take some samples over S0 for a number of times, and pick the best sample. The hope is to find a good approximate solution with reasonable chance. In this talk, we set out to present a number of scenarios for f, S and S0 where certain probability bounds can be established, leading to a quality assurance of the procedure. For example, if f is a homogeneous polynomial of degree d in n variables and F is its corresponding symmetric tensor, and x_i (i = 1, 2, ..., n) are random variables taking 1 or -1 based on independent coin tossing, then Prob{ f(x_1, x_2, ..., x_n) > c1 n^{-d/2} \|F\|_1 } > c2, where c1, c2 are two positive universal constants. Several new inequalities concerning probabilities of the above nature are presented. Moreover, the bounds are tight in most cases. Applications of the results in polynomial optimization are discussed as well.