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

P. Mathieu

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


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


Please log in or register to leave a comment

There are no comments yet