Random sampling is a simple but powerful method in statistics and the design of randomized algorithms. In a typical application, random sampling can be applied to estimate an extreme value, say maximum, of a function $f$ over a set $S\subseteq \mathbb{R}^n$. To do so, one may select a simpler (even finite) subset $S_0\subseteq S$, randomly take some samples over $S_0$ 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 $S_0$ where certain probability bounds can be established, leading to a quality assurance of the procedure. For example, if $f$ is $d$-th order homogeneous polynomial in $n$ variables and $F$ is its corresponding super-symmetric tensor, and $\xi_i (1\le i\le n)$ are i.i.d. Bernoulli random variables taking $1$ or $-1$ with equal probability, then $\Prob\left\{f(\xi_1,\xi_2,\cdots,\xi_n)\ge c_1 n^{-\frac{d}{2}} \|F\|_1\right\} \ge c_2$, where $c_1,c_2>0$ are two 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 optimization are discussed as well.