Music generated by random walk from a statistical model generally fails to capture the style and quality of music in its training corpus. In the context of melody harmonization, this paper first demonstrates that violations of general rules of harmony are clearly related to cross-entropy. The paper then describes and evaluates an improved random walk method which efficiently samples low cross-entropy harmonizations. Applying the method, the relationship between cross-entropy and harmonization quality becomes even more apparent. These results will impact on future work in music generation from statistical models.