Markov Factors on Average -- an L_infty Case