A Dikin walk is a Markov chain for sampling from a convex set using proposals adapted to a local metric
from an interior-point barrier. In the Gaussian version, the proposal at 
is a multivariate
normal distribution with covariance matrix
proportional to 
,
where 
is the local metric. A Metropolis-Hastings
accept-reject correction gives the desired stationary
distribution (Lu 2026).
Lu (2026) proved a 
iteration bound for the half-lazy Gaussian Dikin walk based on a polylogarithmically
rescaled Lee-Sidford metric on a bounded full-dimensional polytope 
. The target probability
density function is proportional to 
on 
, including the uniform
distribution when 
.
The initial law must have finite chi-square divergence from the target, meaning that
for its density
relative to the target law 
. The bound suppresses logarithmic factors in the dimension,
number of inequalities, initial divergence, and error tolerance. It counts Markov
chain iterations, not the arithmetic cost of constructing the metric. Lu (2026)
attributes the proof to ChatGPT 5.6 Pro and states that
he verified it.
