Internal Validity and Random Assignment
Internal validity depends on random assignment, where chance determines whether a user arriving for testing gets the A or B version of the UI. This is easy enough to achieve by using a pseudorandom number generator to set the UI for each user’s session. You’re describing difficulties in tracking a user between sessions, but since data for an A-B test occurs in a single session, that’s irrelevant. As long as you can track the users in a single session (e.g., by user account or IP address), there is no problem.
If you’re concerned with the same users taking the A-B test twice, that's not a factor in internal validity. The logic of internal validity requires that users in the A and B group be statistically equivalent, as ensured by random assignment. Whether a user appears in the same group twice or in each group once doesn’t matter as long as the probabilities are equal for everyone (e.g., you’re equally likely to get repeat users in Group A as Group B).
External Validity and Random Sampling
It’s a myth that external validity depends on random sampling, where each user in the population has an equal chance of inclusion in the test sample. External validity depends on representative sampling, where the users in sample are on average the same on all relevent dimensions as the users in the population. The confusion between the two is due to random sampling being the way to ensure you have a perfectly statistically representative sample.
But do you need a perfectly representative sample? Or is your sample representative enough that it is reasonable to generalize the findings from your sample to a particular population? Don’t fall into the trap of thinking that, because we “just don’t know” how the sample and population might be different, there is no external validity. If I exclude users who use ad blockers, is there really a serious reason to believe they will perform differently on average than the users you included? If the A-B test assesses response to ads (or ad-like things), I’d say yes. If the A-B test assesses the response to the order of menu items, I’d say no. It’s a judgement call.
It can also be mitigated. If there is a good reason to believe the population might be different than the sample on some dimension that could affect the results, measure it. For example, it’s reasonable to argue that users with ad blockers are more savvy and experienced with the web, so would do better with a UI with more expert features. So, compare the accounts of those in and not in the A-B test and see if there is evidence of different expertise (e.g., frequency of use of the app, changing of default settings). If there’s no difference, don’t worry about it. If there is, then separately analyze the expert users in your sample (there’ll be some) from the non-experts, and see if there is a performance difference.
If you’re concerned about the impact of repeat users on your inferential statistics, don’t be. Nearly all inferential statistics assume random sampling with replacement. Usability testers and researchers may take steps to exclude repeat participants, but that’s primarily because it doesn’t “look good” (face validity), and because it’s generally assumed that the real population (which usually includes all potential users, not just current users) is so enormous that a repeat participant is extremely unlikely.
I recommend you take steps to prevent repeat users by the methods you describe (especially since sites typically have some very heavy users and a long tail of use-it-once users), but I wouldn’t worry about a handful repeat users who thwart your efforts out of the 100s or 1000s of participants typical in an A-B test sample. Which method you use to prevent repeat users depends on your particular test and the reasonable implications for sampling bias. For example, if the A-B test period is only a week, and typical users only use the site once a month, then you can expect a insignificantly small proportion of users to use the site twice in one week and happened to clear their cookies between sessions.
Validity Isn’t Binary
Validity is not a binary variable, but is a question of degree or judgement. I sometimes see a tendency for people to spot a single flaw in research, like an A-B test, and conclude the research is completely invalid. Nothing works that way. No research is perfect, but that doesn’t make all research worthless, especially compared to the alternative of an intuitive guess. Any piece of research is “evidence” of a particular strength for a certain conclusion. It is never “proof” of a conclusion and rarely total crap either.
When you see a weakness in research, you need to ask yourself, what are the implications in this particular case? Is it a fatal flaw? Does it reduce confidence enough that you want follow-up research (e.g., go ahead with the winner in an A-B test, but monitor its performance)? Does it merely reduce confidence from 98% to 95%? Does it, in fact, strengthen the results?
This is true even for internal validity. I would not reject a correlational study out of hand. Yes, it won’t have the near-perfect internal validity of an A-B test, but that doesn’t mean it has zero internal validity. I would look closely at the pattern of data, and ask myself how reasonable the implied causation is, what other possible paths of causation are reasonable, and what evidence rules them out, then reach a certain level of confidence in the conclusion.
