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