Comparing Non-deterministic Binary Classifiers
A good strategy is to do n times k-fold cross validation, which should give a pretty good estimation of the average performance of both algorithms. What this means is you perform your k-fold cross validation n times, with different random folds each time, and average the results. People commonly use k = n = 10, but the higher the values of k and n the better.