[math-fun] Can carries create correlations?
Can we show the middle bit of a product of a random integer with another integer is random? Motivating application: We¹re doing a long series of experiments where in each experiment we need to randomly assign statistically half the members of a population to a control group and the other half to a test group. We don't want the assignments to be correlated across different experiments. Further, we happen to have a random K-bit integer N assigned to each member. How many independent experiments can these N help us do? Obviously we can do K, by extracting the M-th bit of N, 0<=M<=K, to define group assignments in the M-th experiment. And of course we can do 2^K-1, using the parity of the bitwise AND of M & N, 1<=M<=2^K-1. XORing a bunch of random bits seems clearly unbiased. Now, as an alternative to the AND-and-parity calculation, can we instead justify just taking the "middle bit" of the double-wide product M * N? The middle bit is essentially the XOR of N and bit-reversed M, plus carries. So the XOR contribution is the same as with the AND-and-parity approach, but can carries create correlations?
Why not use a cryptographic hash function? --ms On 2013-08-10 12:09, Marc LeBrun wrote:
Can we show the middle bit of a product of a random integer with another integer is random?
Motivating application: We¹re doing a long series of experiments where in each experiment we need to randomly assign statistically half the members of a population to a control group and the other half to a test group. We don't want the assignments to be correlated across different experiments.
Further, we happen to have a random K-bit integer N assigned to each member.
How many independent experiments can these N help us do?
Obviously we can do K, by extracting the M-th bit of N, 0<=M<=K, to define group assignments in the M-th experiment.
And of course we can do 2^K-1, using the parity of the bitwise AND of M & N, 1<=M<=2^K-1. XORing a bunch of random bits seems clearly unbiased.
Now, as an alternative to the AND-and-parity calculation, can we instead justify just taking the "middle bit" of the double-wide product M * N?
The middle bit is essentially the XOR of N and bit-reversed M, plus carries.
So the XOR contribution is the same as with the AND-and-parity approach, but can carries create correlations?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
MLB> ... we happen to have a random K-bit integer N assigned to MLB> each member. How many independent experiments can MLB> these N help us do? Obviously we can do K, ... MS> Why not use a cryptographic hash function? I think Mike is on the right track; there is no reason to do any designing unless you need high efficiency. What you need is a stream cipher that evolves each N into an arbitrary number of bits. Hashing the concatenation of N and the experiment number and taking however many bits you want should do fine. An only slightly different proposal is to use a block cipher to construct a stream cipher with counter mode. Here is one proposal. Take a block cipher (I think any of the standard ones will do): use N as the key and the experiment number as the input and take as many bits as you like from the output. Do you need something faster that that? Whit
participants (3)
-
Marc LeBrun -
Mike Speciner -
Whitfield Diffie