Log-Sobolev and Spectral Gap Inequalities for the Knapsack Markov Chain

P. Mathieu

2002, v.8, Issue 4, 595-610

ABSTRACT

We study a random walk moving on a discrete cube of large dimension and subject to a linear constraint. Under the assumption that more than the half of the points in the cube satisfy the constraint, we prove log-Sobolev and Poincare inequalities with constants of the correct order.

Keywords: knapsack problem,log-Sobolev inequalities,spectral gap,generalized Poincare inequalities

COMMENTS

Please log in or register to leave a comment

There are no comments yet

Laboratory of large random systems, Dept. of Mechanics and Mathematics
Moscow State University, Vorobievy Gory, 119952 Moscow Russia
E-mail: editor@math-mprf.org
Please enter our email addresses to the list of allowed addresses of your mail server

The journal was founded in 1995 by prof. Malyshev V. A.
Published by Polymat Publishing Company, Moscow, Russia
ISSN 1024-2953
The journal is published quaterly

Markov Processes And Related Fields

Scientific Journal

Submit article

P. Mathieu