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

P. Mathieu

2002, v.8, №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