Appropriate use of z test comparing two proportions (Apologies for the cross-posting from math.stackexchange.com; I wasn't aware of this site until just now).
I would like to test the performance of two algorithms. The second is a variant of the first. There is no prior data on the performance of either in a particular domain. The performance of both on any given sample is judged on a simple binary classification of success or failure.
My null hypothesis is that there is no difference in the performance of the two algorithms. My alternative hypothesis is that the second performs better.
I obtained $n$ samples and both algorithms' result on each sample was evaluated. I ended up with a proportion of success for both algorithms.
Does the fact that the algorithms operated independently on the samples mean that I am now justified in using the $z$ test for comparing two proportions? Or should I have split $n$ and run a given algorithm against a portion of $n$, and the other algorithm on the other portion? Due to operational constraints the samples were/are difficult to collect, and splitting $n$ is extremely unpalatable. I also would like to be able to compare the samples directly against each other in order to get some idea of the second algorithm's limitations.
What are my options? Is there some other variant of a $z$ test that applies here? Since $n$ was small to start with, should I just throw up my hands and declare this a pilot study? If I do in fact do that, am I then justified in using the $z$ test for two proportions?
Any input is greatly appreciated. I'm kicking myself for not having thought this out beforehand. As you can tell, I'm not exactly an academic in this field.
 A: As mentioned above, your scenario appears to have a natural pairing. You could use a Z test, but a simple alternative is McNemar's test. This test will likely be more powerful than the Z test.
A: 1) Your data look to be paired. You shouldn't ignore this
2) The usual proportions test assumes a constant 'success' rate across observations (the things you're testing the algorithms on). This doesn't sound like it will be the case.
You might want to consider the test cases as randomly chosen from the population of possible ones that you want to extend your inference to - to treat the test sets as random effects in a mixed model.
If your success rate is constant, you could maybe do a two-sample (possibly one-tailed) proportions test (though if the sample size is small you might consider doing it as exact binomial rather than the normal approximation, since the approximation may not be good).
If you condition on the test sets but they have different success rates, then you have something that could perhaps be done as a chi-square (though you could work out a one-tailed test if you really need that).
If you do treat the impact of the data sets you test on as a random effect, you'll need a mixed-model logistic regression (i.e. a GLMM). 
