Log-Sobolev and Spectral Gap Inequalities for the Knapsack Markov Chain
2002, v.8, №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