Variance of the Random k-SAT Hitting Time

Let H${}_n$ be the index of the first unsatisfiable prefix in random k-SAT on n variables, with independent uniformly signed clauses using k distinct variables and sampled with replacement. For every fixed k ≥ 4, we prove $\mathrm{Var}(H_n)={\Theta }_k(n)$. For k = 3, the variance is bounded below by a positive multiple of n and above by a constant multiple of $n\log n$; the companion paper on random 3-SAT sharpens this to $\Theta (n)$. The same upper bounds proved here hold after clipping at any fixed positive multiple of n.