Aspects of Mass Transportation in Discrete Concentration Inequalities
We prove that the modified log-Sobolev inequality implies the transportation inequality in the first systematic comparison of the modified log-Sobolev inequality, the Poincaré inequality, the transportation inequality, and a new variance transportation inequality. The duality shown by Bobkov and Götze of the transportation inequality and a generating function inequality is then utilized in finding the asymptotically correct value of the subgaussian constant of a cycle, regardless of the parity of the length of the cycle. This result tensorizes to give a tight concentration inequality on the discrete torus. It is interesting in light of the fact that the corresponding vertex isoperimetric problem has remained open in the case of the odd torus for a number of years. We also show that the class of bounded degree expander graphs provides an answer, in the affirmative, to the question of whether there exists an infinite family of graphs for which the spread constant and the subgaussian constant differ by an order of magnitude.
Finally, a candidate notion of a discrete Ricci curvature for finite Markov chains is given in terms of the time decay of the Wasserstein distance of the chain to its stationarity. It can be interpreted as a notion arising naturally from a standard coupling of Markov chains. Because of its natural definition, ease of calculation, and tensoring property, we conclude that it deserves further investigation and development. Overall, the thesis demonstrates the utility of using the mass transportation problem in discrete isoperimetric and functional inequalities.
Advisor:Michael Loss; Thomas Morley; Ellis Johnson; Wilfrid Gangbo; Prasad Tetali
School Location:USA - Georgia
Source Type:Master's Thesis
Date of Publication:04/26/2005