From: jbriggs444 on
On Aug 13, 8:29 am, jbriggs444 <jbriggs...(a)gmail.com> wrote:
> On Aug 13, 4:27 am, orz <cdh...(a)gmail.com> wrote:
>
> > on topic again:
>
> > Is there any reason to have walls in the system instead of wrap around
> > coordinates?
>
> If you have walls and corners, does that bias your results?
>
> Let's see...
>
> We are looking for 4-tuples with each element selected from
> the set {-1, 0, 1} subject to the constraints that:
>
> 1.  Not all elements can be zero
> 2.  The x element cannot be -1.
>
> There should be ( 81 - 27 ) / 2 such elements.  We want to
> ensure that the parity of these elements is evenly split between
> even and odd.
>
> Ahah!  An easy argument follows.  We already know that the
> three dimensional (3x3x3) hyper-plane right at the wall is not
> evenly split with respect to parity.  And we already know that
> the full four dimensional (3x3x3x3) hyper-cube is evenly split.
> And we can easily see that the two four-dimensional half-cubes
> with the center plane excluded are mirror images of one
> another and must neccessarily have an identical parity excess.
>
> It follows that eliminating one four-dimensional half-cube
> at the walls will have the effect of inducing a parity bias
> there.
>
> So yes, non-toroidal walls are a problem.

Making this more concrete...

You start with a 3x3x3x3 hyper-cube with the center
cell eliminated. 40 of these cells have even parity and
40 have odd parity.

The hyper-plane right at the wall is a 3x3x3 cube with
the center cell eliminated. It has a 14 to 12 parity
bias.

Of the original 80 cells, 26 are in the "at-the-wall"
cube. 27 more are on the far side of the wall and
27 more are on the near side of the wall.

Both of these cubes have a 13 to 14 parity bias
in the opposite direction of the central hyper-plane.

14 to 12 plus 13 to 14 = 27 to 26.

So the walls of the four dimensional matrix
naively induce a 27 to 26 bias in the random bits
generated there.

However, that analysis may indeed be quite naive.
Unless I am mistaken, the likelihood of finding
a particle adjacent to a wall is lower than the
likelihood of finding it somewhere in the interior of
the matrix. You can easily see this if you reduce
things to one dimension and use a matrix that is
three cells wide. You get an asymptotic density
of (0.25, 0.50, 0.25).

I'm just an untutored dweeb, but it seems you'd want
some Markov analysis to come up with an asymptotic
density for a walled four-dimensional space.

Or just run a simulation and let a starting distribution
relax through a couple of million iterations.
From: Lev Dymchenko on
On Aug 13, 4:46 pm, jbriggs444 <jbriggs...(a)gmail.com> wrote:
> On Aug 13, 8:29 am, jbriggs444 <jbriggs...(a)gmail.com> wrote:
>
>
>
>
>
> > On Aug 13, 4:27 am, orz <cdh...(a)gmail.com> wrote:
>
> > > on topic again:
>
> > > Is there any reason to have walls in the system instead of wrap around
> > > coordinates?
>
> > If you have walls and corners, does that bias your results?
>
> > Let's see...
>
> > We are looking for 4-tuples with each element selected from
> > the set {-1, 0, 1} subject to the constraints that:
>
> > 1.  Not all elements can be zero
> > 2.  The x element cannot be -1.
>
> > There should be ( 81 - 27 ) / 2 such elements.  We want to
> > ensure that the parity of these elements is evenly split between
> > even and odd.
>
> > Ahah!  An easy argument follows.  We already know that the
> > three dimensional (3x3x3) hyper-plane right at the wall is not
> > evenly split with respect to parity.  And we already know that
> > the full four dimensional (3x3x3x3) hyper-cube is evenly split.
> > And we can easily see that the two four-dimensional half-cubes
> > with the center plane excluded are mirror images of one
> > another and must neccessarily have an identical parity excess.
>
> > It follows that eliminating one four-dimensional half-cube
> > at the walls will have the effect of inducing a parity bias
> > there.
>
> > So yes, non-toroidal walls are a problem.
>
> Making this more concrete...
>
> You start with a 3x3x3x3 hyper-cube with the center
> cell eliminated.  40 of these cells have even parity and
> 40 have odd parity.
>
> The hyper-plane right at the wall is a 3x3x3 cube with
> the center cell eliminated.  It has a 14 to 12 parity
> bias.
>
> Of the original 80 cells, 26 are in the "at-the-wall"
> cube.  27 more are on the far side of the wall and
> 27 more are on the near side of the wall.
>
> Both of these cubes have a 13 to 14 parity bias
> in the opposite direction of the central hyper-plane.
>
> 14 to 12 plus 13 to 14 = 27 to 26.
>
> So the walls of the four dimensional matrix
> naively induce a 27 to 26 bias in the random bits
> generated there.
>
> However, that analysis may indeed be quite naive.
> Unless I am mistaken, the likelihood of finding
> a particle adjacent to a wall is lower than the
> likelihood of finding it somewhere in the interior of
> the matrix.  You can easily see this if you reduce
> things to one dimension and use a matrix that is
> three cells wide.  You get an asymptotic density
> of (0.25, 0.50, 0.25).
>
> I'm just an untutored dweeb, but it seems you'd want
> some Markov analysis to come up with an asymptotic
> density for a walled four-dimensional space.
>
> Or just run a simulation and let a starting distribution
> relax through a couple of million iterations.- Hide quoted text -
>
> - Show quoted text -

If we have cube size 4, most particles are near walls btw.
From: Cristiano on
orz wrote:
> I have not been very impressed with Diehard or the NIST stuff or RaBiGeTe
> or ENT.

As I told you, I got little feedback for RaBiGeTe. What should I do to get
RaBiGeTe more "impressive"?

Cristiano


From: Lev Dymchenko on
On Aug 13, 7:20 pm, "Cristiano" <cristiaN...(a)gmail.com> wrote:
> orz wrote:
> > I have not been very impressed with Diehard or the NIST stuff or RaBiGeTe
> > or ENT.
>
> As I told you, I got little feedback for RaBiGeTe. What should I do to get
> RaBiGeTe more "impressive"?
>
> Cristiano

I tested mdwp with RaBiGeTi, I have some small suggestions for the
test.
From: orz on
Cristiano, and anyone else interested in statistical tests for RNGs:

I'd like to talk more about that, but don't really want to sidetrack
this thread. I could email people individually, but I'd like a more
public exchange where more people might join the conversation. So,
I'm creating a new thread in sci.math with the title of "statistical
tests for random number generators" and reply to that stuff there.
I'll try to cross-post it to sci.crypt.random-numbers since that seems
to be the only usenet group specific to RNGs, even if it is slightly
offtopic for crypto stuff.