|
|
 | | From: | David Bernier | | Subject: | question related to RAND corp.'s "1 million random digits" | | Date: | Thu, 13 Jan 2005 11:54:52 -0500 |
|
|
 | According to:
http://www.rand.org/publications/classics/randomdigits/ ,
their 20,000 cards with 50 digits/card were not "random enough", and
they "rerandomized" their data by adding digit no. 1 of card
1 to digit no. 1 of card 2 and taking the remainder mod 10,
and so on for the pairs of cards (2,3), ... (19999, 20000),
(20000, 1). { and similarly for digits nos. 2, 3, ... 50}
My question can be framed in terms of linear algebra over
the ring R = Z/(10Z):
If f: R^(20000) -> R^(20000) is defined by
f(d1, ... d20000) = (d1, d2, ..., d20000) + (d2, d3, ... d20000, d1),
is it true that f(x1, x2, ... x20000) = (a1, a2, ... a20000)
where (a1, a2, ... a20000) is a given or known,
has either 0 or 2 solutions?
As a special case, if (a1, a2, ... a20000) = ([0], ... [0]),
I can only think of the solutions
([0], ... [0]) and ([5], ... [5]).
David Bernier
P.S.: inspired in part by comp.compression articles by
Matt Mahoney and Phil Carmody.
|
|
| | From: | Matt Mahoney | | Subject: | Re: question related to RAND corp.'s "1 million random digits" | | Date: | 13 Jan 2005 13:04:11 -0800 |
|
|
| David Bernier wrote:
> According to:
> http://www.rand.org/publications/classics/randomdigits/ ,
>
> their 20,000 cards with 50 digits/card were not "random enough", and
> they "rerandomized" their data by adding digit no. 1 of card
> 1 to digit no. 1 of card 2 and taking the remainder mod 10,
> and so on for the pairs of cards (2,3), ... (19999, 20000),
> (20000, 1). { and similarly for digits nos. 2, 3, ... 50}
>
> My question can be framed in terms of linear algebra over
> the ring R = Z/(10Z):
>
> If f: R^(20000) -> R^(20000) is defined by
> f(d1, ... d20000) = (d1, d2, ..., d20000) + (d2, d3, ... d20000, d1),
>
> is it true that f(x1, x2, ... x20000) = (a1, a2, ... a20000)
> where (a1, a2, ... a20000) is a given or known,
> has either 0 or 2 solutions?
>
> As a special case, if (a1, a2, ... a20000) = ([0], ... [0]),
> I can only think of the solutions
> ([0], ... [0]) and ([5], ... [5]).
>
> David Bernier
>
> P.S.: inspired in part by comp.compression articles by
> Matt Mahoney and Phil Carmody.
If there are an odd number of cards, then there are 2 solutions. If
there are an even number, then there are 10 solutions (unfortunately).
-- Matt Mahoney
|
|
| | From: | David Bernier | | Subject: | Re: question related to RAND corp.'s "1 million random digits" | | Date: | Thu, 13 Jan 2005 21:03:23 -0500 |
|
|
| Matt Mahoney wrote:
> David Bernier wrote:
>
>>According to:
>>http://www.rand.org/publications/classics/randomdigits/ ,
>>
>>their 20,000 cards with 50 digits/card were not "random enough", and
>>they "rerandomized" their data by adding digit no. 1 of card
>>1 to digit no. 1 of card 2 and taking the remainder mod 10,
>>and so on for the pairs of cards (2,3), ... (19999, 20000),
>>(20000, 1). { and similarly for digits nos. 2, 3, ... 50}
>>
>>My question can be framed in terms of linear algebra over
>>the ring R = Z/(10Z):
>>
>>If f: R^(20000) -> R^(20000) is defined by
>>f(d1, ... d20000) = (d1, d2, ..., d20000) + (d2, d3, ... d20000, d1),
>>
>>is it true that f(x1, x2, ... x20000) = (a1, a2, ... a20000)
>>where (a1, a2, ... a20000) is a given or known,
>>has either 0 or 2 solutions?
>>
>>As a special case, if (a1, a2, ... a20000) = ([0], ... [0]),
>>I can only think of the solutions
>>([0], ... [0]) and ([5], ... [5]).
>>
>>David Bernier
>>
>>P.S.: inspired in part by comp.compression articles by
>> Matt Mahoney and Phil Carmody.
>
>
> If there are an odd number of cards, then there are 2 solutions. If
> there are an even number, then there are 10 solutions (unfortunately).
> -- Matt Mahoney
I redid your alternating sum test on 50 sequences of 20,000 digits each,
as: d1 - d2 + d3 - d4 + ... - d_20,000 and I also get 50 even sums but
only about 9 sums that are divisible by 10... (unfortunately).
It would be nice if some NSA mathematicians could look at
this stuff and be allowed to speak publicly about it.
David Bernier
|
|
| | From: | Matt Mahoney | | Subject: | Re: question related to RAND corp.'s "1 million random digits" | | Date: | 14 Jan 2005 06:43:44 -0800 |
|
|
| David Bernier wrote:
> I redid your alternating sum test on 50 sequences of 20,000 digits
each,
> as: d1 - d2 + d3 - d4 + ... - d_20,000 and I also get 50 even sums
but
> only about 9 sums that are divisible by 10... (unfortunately).
> It would be nice if some NSA mathematicians could look at
> this stuff and be allowed to speak publicly about it.
>
> David Bernier
I doubt the NSA could help if the cards were shuffled. If you swap two
cards with the same sign (for example d3 and d5), then the sum is still
0 mod 10. So even if you could find an assignment of weights (1 or -1)
to the shuffled cards that sums to 0 mod 10, you've only reduced the
number of possible permutations from 20000! to 10000!^2
-- Matt Mahoney
|
|
|
