A/B testing is a form of randomized experiment that is used by many companies to learn

Chapter 2, Problem 63

(choose chapter or problem)

A/B testing is a form of randomized experiment that is used by many companies to learn about how customers will react to dierent treatments. For example, a company may want to see how users will respond to a new feature on their website (compared with how users respond to the current version of the website) or compare two dierent advertisements. As the name suggests, two dierent treatments, Treatment A and Treatment B, are being studied. Users arrive one by one, and upon arrival are randomly assigned to one of the two treatments. The trial for each user is classified as success (e.g., the user made a purchase) or failure. The probability that the nth user receives Treatment A is allowed to depend on the outcomes for the previous users. This set-up is known as a two-armed bandit. Many algorithms for how to randomize the treatment assignments have been studied. Here is an especially simple (but fickle) algorithm, called a stay-with-a-winner procedure: (i) Randomly assign the first user to Treatment A or Treatment B, with equal probabilities. (ii) If the trial for the nth user is a success, stay with the same treatment for the (n + 1)st user; otherwise, switch to the other treatment for the (n + 1)st user. Let a be the probability of success for Treatment A, and b be the probability of success for Treatment B. Assume that a 6= b, but that a and b are unknown (which is why the test is needed). Let pn be the probability of success on the nth trial and an be the probability that Treatment A is assigned on the nth trial (using the above algorithm). (a) Show that pn = (a b)an + b, an+1 = (a + b 1)an + 1 b. (b) Use the results from (a) to show that pn+1 satisfies the following recursive equation: pn+1 = (a + b 1)pn + a + b 2ab. (c) Use the result from (b) to find the long-run probability of success for this algorithm, limn!1 pn, assuming that this limit exists.