Conference rusure::math

    Re .0:
    
    I don't think the problem is well-defined.  Spheres can be packed in a
    variety of ways, and I don't think the best packing is known.  The way
    marbles are touching would affect the probability.  If a particular
    connectivity for the marbles were known, we might be able to do
    something with this problem.
    
    
    				-- edp
    
    
Public key fingerprint:  8e ad 63 61 ba 0c 26 86  32 0a 7d 28 db e7 6f 75
To find PGP, read note 2688.4 in Humane::IBMPC_Shareware.

Re: .1  (edp)
    
>    I don't think the problem is well-defined.  Spheres can be packed in a
>    variety of ways, and I don't think the best packing is known.  The way
>    marbles are touching would affect the probability.  If a particular
>    connectivity for the marbles were known, we might be able to do
>    something with this problem.
    
Suppose I simplify the problem by specifying that the marbles are all packed
on a perfect grid, such that each marble is considered adjacent to 3^3-1 = 26
other marbles, like the cubes that make up a Rubik's cube puzzle.

Also, let us assume that R >> N, so that we can neglect boundary problems at
the surface of the sphere of packed marbles. 

> Suppose I simplify the problem by specifying that the marbles are all packed
> on a perfect grid, such that each marble is considered adjacent to 3^3-1 = 26
> other marbles, like the cubes that make up a Rubik's cube puzzle.

    The normal meaning of "marble" implies a spherical shape. In which case
    you cannot pack 27 marbles in a Rubik's cube shape and have the center
    marble touching the 12 corners.
    
    So is it: (a) square marbles, (b) 14 adjacencies per rubic or (c) a
    very loose definition of "adjacent"?
    
      John

Re: .3  (John)

>    The normal meaning of "marble" implies a spherical shape. In which case
>    you cannot pack 27 marbles in a Rubik's cube shape and have the center
>    marble touching the 12 corners.
>    
>    So is it: (a) square marbles, (b) 14 adjacencies per rubic or (c) a
>    very loose definition of "adjacent"?
    
(c) a loose definition of "adjacent", such that if 27 marbles were packed in
a Rubik's cube, we will consider 26 marbles as being adjacent to the center
one. 

It sounds like (a) square marbles would also fit the bill, as long as they are
all lined up on a perfect grid in any dimension, yes?

So if I understand the problem, as restated, I am looking at a cubic grid 
of wires, running in X, Y and Z directions.  The wires are one unit apart
and the number of wires is much larger than N.  Each vertex is painted with
one of four colors, red, green, yellow or blue.  Two vertices are adjacent if
the distance between them is less than the cube root of 3.  A cluster is a set
of vertices, such that any two vertices in the cluster can be connected by
a set of steps between adjacent vertices.

The question is, what is the probability of finding a cluster of size N?

After all this, it turns out we need to know something else: assume that the
probability of a given vertex being a given color is exactly 1/4.

To get a cluster of size 1, 26 adjacent vertices must be of a different
color.  The probability is (3/4)^26 = 0.0005644, according to my calculator.

To get a cluster of size 2, K adjacent vertices... , where K depends on the
geometry of the pair.  If the two vertices are on the same wire, K is 26+9=35,
and the probability is 0.0000424.

You can see where this is going.  The more vertices in the cluster, the more 
vertices adjacent to the cluster, and the more opportunity for a vertex of 
the same color.  As long as N is small compared to the number of vertices, 
the probability is high of getting a cluster with large N.

I forgot one step in the calculation.

Call V the number of vertices.  

The probability that a given vertex is red is 1/4, so there are about V/4 
opportunities for a red cluster of size N=1.  As long as V/4 is large compared
to 1/0.0005, the probability is high of finding at least one cluster of size 1.

For a size 2 cluster, V/16 must be large compared to 1/0.00004.

As long as V is large, the probabilities involved approach 1.

A more interesting question might be something like this: given a red vertex,
what is the probability that it is a member of a cluster of size N?

I believe that this problem is one of those which depend critically on
dimension.  In one dimension this is just the usual problem of distributions
of runs, aka gambler's ruin.  In three dimension, I think this is a problem
studied by materials science and geology.  As I remember, they use numerical
methods, not analytic.

In three dimensions, this is an interesting problem for people
who drill oil wells.  Each vertex can contain either rock or
a void.  What's the expected volume of connected voids that
will be connected to the spot where you sink a drill?  As I
recall, this is a very steep function of the probability that
a given location is a void.  Slightly below a critical value, and
you find most voids aren't connected to each other.  Slightly
above, and you find almost all the voids are connected.

.6>A more interesting question might be something like this: given a red vertex,
.6>what is the probability that it is a member of a cluster of size N?

    Or perhaps: what is the distribution of cluster sizes for large V?
    		what effect does increaseing the number of colors have?
    
    This would be a good problem to handle with simulation and a large
    virtual address space.
    
      John