Random but even distribution of AB v. BA

Question

I'm a software developer not a statistician, so use small words. :)

I'm looking for an algorithm to generate a sequence of AB tests that are randomly distributed to users, but ensures an equal distribution. The sequence must be reproducible using a seed value.

(I'll get around to actually finding a software algorithm, but first I need to understand/clarify what I'm trying to do.)

So: 6 subjects or 50 or 500 (always an even number).

• Exactly half the subjects must get test A then test B, the other half must get B then A.
• The profile cannot be simply AAABBB, since the subject list is not necessarily randomized.
• It needs to be reproducible. So, a "seed" number will ensure I can get that exact same distribution again.
• The seed also ensures I can guarantee a different sequence if that's what I want.

My first shot at this involves a random profile where the second half is "flipped", ensuring it's symmetrical.

So: 20 subjects, Seed = 314

My simple algorithm just runs through the seed, toggling A to B until it hits the halfway point, then reverses the sequence:

3     1 4       3...      
A A A B A A A A B B (flip) A A B B B B A B B B
B B B A B B B B A A        B B A A A A B A A A
                          ...3 4       1 3

One of the things I've run up against is that, for a small number such as 6, a seed number must be highly constrained, or several different seeds will result in the same profile.

So: 6 subjects, Seed = 523

5...
A A A (flip) B B B
B B B        A A A
              ...5

but seed 427 does the same thing:

4...
A A A (flip) B B B
B B B        A A A
              ...5

(In fact, there are so few possible permutations of profiles, the seed itself must be constrained to no more than about 24 or so possible values. Not really a seed anymore. More like 'pick a number from 1 to 24')

Answer 1

What you are asking for is called randomized permuted blocks in the statistical design of experiments.

Blocking is used to ensure that treatments (or in your case, treatment sequences) are equally distributed among experimental units even though their assignment is random. So for example, if you choose a block size of $2$, you would have blocks of the form $$\text{Block 1} = ((A,B), (B,A)), \quad \text{Block 2} = ((B,A), (A,B)).$$ Then for $2n$ subjects, you would choose a randomly generated list of $n$ blocks, and assign pairs of subjects accordingly. So for example, with $2n = 10$ subjects, you would generate a random list of $5$ blocks, say $$(1,2,1,1,2),$$ and then you would obtain the treatment sequence assignment $$((A,B), (B,A), (B,A), (A,B), (A,B), (B,A), (A,B), (B,A), (B,A), (A,B)).$$ This means that for a block size of $2$ and $10$ subjects, you have $2^5 = 32$ possible randomized assignments.

You can choose larger blocks, of course, but the block size must be an even number to maintain balance. So the next block size up, $4$, would consist of the list $$\begin{align*} \text{Block 1} &= ((A,B), (A,B), (B,A), (B,A)) \\ \text{Block 2} &= ((A,B), (B,A), (A, B), (B,A)) \\ \text{Block 3} &= ((A,B), (B,A), (B,A), (A,B)) \\ \text{Block 4} &= ((B,A), (A,B), (A,B), (B,A)) \\ \text{Block 5} &= ((B,A), (A,B), (B,A), (A,B)) \\ \text{Block 6} &= ((B,A), (B,A), (A,B), (A,B)). \end{align*}$$ This is because there are $\binom{4}{2} = 6$ ways to order $2$ distinct treatment sequences among $4$ subjects in a block. Then for a sample size of $6n$, you would have $6^n$ possible randomized assignments that are perfectly balanced, and you would generate these with a random list of $n$ integers from $1$ to $6$; for example, for a sample size of $6n = 60$, you could generate the list $$(3, 3, 6, 1, 2, 1, 5, 1, 3, 6).$$ Note that we do not need an even distribution of the blocks themselves, because it is within each block that the assignment of treatments is equally distributed. But we do need to randomly choose each of the $6$ blocks with equal probability.

Larger block sizes have the advantage of permitting longer runs of the same treatment sequence, thus the resulting randomization can exhibit more variation in assignment while maintaining balance. So for example, a block size of $10$ could admit the assignment $$((A,B), (A,B), (A,B), (A,B), (A,B), (B,A), (B,A), \ldots),$$ whereas a block size of $2$ cannot. However, a disadvantage of large blocks is that your sample size must be a multiple of the number of blocks in order to maintain perfect balance.

Answer 2

A very elegant, but certainly not obvious, method is to use the golden ratio to select your samples, where the golden ratio, $\phi = \frac{1+\sqrt{5}}{2} = 1.61803399...$

Suppose you have $N$ subjects, numbered from $1$ to $N$, and a seed value, $s$,

Then allocate the $k^{\textrm{th}}$- subject the value, $x_k$ such that: $$ x_k = (s+ k \phi) \; (\textrm{mod}\; 1),$$ where the $(\textrm{mod} \; 1)$ operator that takes the fractional part of argument.

That is, each of the $N$ subjects will be allocated a value of $x_k$ which will always between 0 and 1.

Now simply, allocate those subjects with the lowest $N/2$ scores to Treatment $A$, and those with the highest $N/2$ scores to Treatment $B$.

Note that if computational speed is an issue, instead of sorting all the $x_k$ for all $N$ subjects, you could just pick all those subjects with a value of $x_k < 0.5$ for Treatment A. This will often get exactly the same result and will never be more than 1 count off the ideal 50-50 allocation.

For example, for the seed value of $s=0$, the subjects will be allocated as follows: $$ \{ B,A,B,A,A,B,A,B,B,A,B,A,A,B,A,B,B,A,B,A,... \} $$

Finally, if you wish to take a different sample, simply select a different seed value, $s$.

Python code for this methodology is as follows:

n=50

phi = (1+pow(5),0.5))/2
x = np.zeros(n)                 
s = np.random.uniform(0,1)
for i in range(n):
    x = (s + phi*(i+1)) %1

print (s)
print (x)