Note on the knapsack Markov chain. (Q1888773)

In the knapsack problem, admissible packings \((x_1,\dots ,x_n)\in\! \{0,1\}^n\) are defined by \({\sum \limits_{i=1}^na_ix_i\leq b}\) where \(a_1,\dots ,a_n,b\) are given positive integers. On the assumption that each packing with at most \(\alpha n\) one's is admissible, \(1/2<\alpha \leq 1\), a Markov chain on the set of admissible packings is shown to be rapidly mixing. This follows from a new lower bound on the spectral gap \(1-\beta _1\) where \(\beta _1\) is the second largest eigenvalue of the transition matrix.