Determine if an action increases the proportion of 1s in binary data with unknown population We're trying to improve search results, and we're trying to determine if certain changes (adding a word to a synonym list, removing it from the query, etc) have a statistically significant improvement on the results for future searches.
We currently have data for past queries and their matching "correct" results.  We also have tests to sample from those past queries, perform them again, and look at the percentage of "good matches". A good match being one for which the known correct result is within the top recommendations by the search engine.
For a concrete example: say we want to know if adding a synonym for show->display will improve results.  We look through past queries and find all of those containing the word 'show', then we find the number of good matches.  Then we add the synonym map, and test again for the same sample of queries.
The results let us know how many queries improved, how many got worse, how many stayed the same, total number of samples, and total number of good matches (before and after the test).
To get an idea of the numbers, we have about 260,000 past queries, and for most words there are less than 10,000 queries which contain those words (and thus we can test the entire sample).
For this example the results are:
Sample size containing 'show': 5250 
Good matches (base):           3212
Good matches (test):           3208
Improved:                      8
Got worse:                     12
Total change:                  -4

The question is which test(s) would be the most helpful in determining if this change is likely to represent the change in future unknown queries? (Using a 95% confidence level)
Here's the things I've tried on R, and their results:


*

*Two sample T-test on both sets of data (represented by vectors of 1s and 0s) - not significant

*T-test on the difference of the sets - not significant

*Bootstrapping on the difference in mean of each set, and doing a T-test of that result - significant

*Bootstrapping each sample on their mean, then T-test two sample t-test of the results - significant

*Bootstrapping each sample on their mean, then t-test of the difference in the results - significant

*McNemar test - significant

 A: Since you have paired data, you should be using a paired test. Even with bootstrapping, you have to make sure that you keep the pairing. With binary data, a t-test is really not the best choice. It is reasonable with a big sample size, but there are better targeted tests for binary data. So the test of choice is McNemar's test which is targeted exactly at your situation (paired binary data).
For McNemar's test you have to remember to set up the data correctly. The total should be the number of pairs (5250), and each cell should be one of the Base X / Test Y combinations. Based on your summary, I back-calculated the contents of the table:
> (mm <-  matrix(c(2030, 8, 12, 3200), nr=2))
     [,1] [,2]
[1,] 2030   12
[2,]    8 3200

In mm the rows are Base bad, Base good, and the columns are Test bad, Test good. So 2030 is the number of both bad combinations, 3200 is the number of both good combinations, and 12 and 8 are the number of discrepant results.
> mcnemar.test(mm)

    McNemar's Chi-squared test with continuity correction

data:  mm
McNemar's chi-squared = 0.45, df = 1, p-value = 0.5023

