Graduate Mathematics Tea

You are cordially invited to attend

Concentration of Measures by Size Bias Couplings

Larry Goldstein
USC

Abstract: For a nonnegative random variable $Y$ with finite nonzero mean $mu$, we say that $Y^s$ has the $Y$-size bias distribution if

$$
E[Yf(Y)] = mu Ef[(Y^s)] quad mbox{for all smooth $f$.}
$$

If a bounded size biased coupling for $Y$ exists, that is, if $Y$ can be coupled to $Y^s$ having the $Y$-size bias distribution such that for some constant $C$ we have $|Y^s-Y| le C$ almost surely, then $Y$ satisfies concentration of measure inequalities such as

begin{eqnarray*}
Pleft(frac{Y-mu}{sigma}ge tright)le expleft(-frac{t^2}{2(A+Bt)}right)quadmbox{for all $t > 0$,}
end{eqnarray*}

when $sigma^2=mbox{Var}(Y) in (0,infty)$, $A=Cmu /sigma^2$ and $B=C/2sigma$, when the moment generating function of $Y$ is finite at $2/C$.

Applications of these types of concentration of measure results include the following six examples: the number of lightbulbs switched on at the terminal time in the lightbulb process of Rao, Rao and Zhang, the number of relatively ordered subsequences of a random permutation, sliding window statistics such as the number of $m$-runs in a sequence of independent coin tosses, the number of local maxima of a random function on the lattice, the number of urns containing exactly one ball in the uniform multinomial urn allocation model, and the volume covered by the union of $n$ balls placed uniformly over a volume $n$ subset of $mathbb{R}^d$.

This work is joint with Subhankar Ghosh.