Re: RE: Runs on a Ring

• To: mathgroup at smc.vnet.net
• Subject: [mg32373] Re: [mg32324] RE: [mg32312] Runs on a Ring
• From: Tomas Garza <tgarza01 at prodigy.net.mx>
• Date: Wed, 16 Jan 2002 03:31:15 -0500 (EST)
• References: <200201150730.CAA04513@smc.vnet.net> <000701c19e09\$ece4dac0\$98ee84c3@noos.fr>
• Sender: owner-wri-mathgroup at wolfram.com

```Bonjour Philippe!

Not quite. No reason why they should add up to 1. They are not mutually
exclusive events. You can have at least one run of length 2 and at least one
run of length 3 simultaneously. Take the sequence {1,0,1,1,1,0,1} of length
7, for example. When you form the ring, you get one run of length 2 and one
run of length 3.

Tomas

----- Original Message -----
From: "Philippe Dumas" <dumasphi at noos.fr>
To: mathgroup at smc.vnet.net
Subject: [mg32373] Re: [mg32324] RE: [mg32312] Runs on a Ring

> Buenos dias Tomas
>
> Did you see that you 'experimental' list of frequencies
> {0.0317,0.46995,0.31393,0.15616,0.15603,0.03042}
> sum up to 1.15819 !
> I would have expected a value much closer to 1 given the 100000 tests.
> Isn'it you feeling ?
>
> Philippe Dumas
> 99, route du polygone
> 03 88 84 67 80
> 67100 Strasbourg
>
>
> ----- Original Message -----
> From: <tgarza01 at prodigy.net.mx>
To: mathgroup at smc.vnet.net
> Sent: Tuesday, January 15, 2002 8:30 AM
> Subject: [mg32373] [mg32324] RE: [mg32312] Runs on a Ring
>
>
> > The solution to your problem seems quite difficult. It certainly
requires
> a good familiarity with advanced techniques of combinatorial analysis.
> However, I suggest a procedure to obtain approximate values of the desired
> probabilities using straightforward simulation (and this, I suppose, is
> where Mathematica enters in this case). These values may be useful for
> purposes of checking the analytic solution.
> > Given a sequence of  n sites, fill them at random with 0's and 1's (not
> necessarily equiprobable). If the first and last places have different
> values (i.e., one is 0 and the other is 1), then the number of runs is the
> same for the sequence as for the corresponding ring. But if both have the
> same value, say 1, then the ring (formed by joining the first and last
> values of the sequence) has one extra run of 1's, whose length is the sum
of
> the lengths of the first and the last runs in the sequence, but these two
> runs have then to be deleted.
> > The following function, oneExp[n], performs the experiment of filling a
> sequence of n sites with random 0's and 1's and computes the runs using
> Split. Then it constructs the ring by joining the first and the last runs
> (even when they are of length one) if they have the same value; otherwise
> nothing. Finally, it determines if there is at least one run of 1's of
> length 2, at least one of length 3, and so on until a run of length n,
which
> is the maximum length allowed. So, a typical result of oneExp[n] is a
> sequence of n + 1 0's or 1's, where a 1 in the k-th position means that
> there was at least a run of k 1's in the experiment. A value 1 at the
first
> position means there occurred no 1's at all, and a value of 1 in the last
> position means there occurred all 1's.   The procedure is executed a large
> number of times and the frequency in each position is an approximation to
> the true probability.
> >
> >  In[1]:=
> > sy := Random[Integer, {0, 1}]
> > In[2]:=
> > oneExp[k_] := Module[{lt = k, sam, newsam}, sam = Split[Table[sy,
{lt}]];
> >     Which[Length[sam] == 1 && Union[sam[[1]]] == {0}, newsam =
> Prepend[Table[0, {lt}], 1],
> >      Length[sam] == 1 && Union[sam[[1]]] == {1}, newsam =
Append[Table[0,
> {lt}], 1], True,
> >      newsam = If[Union[First[sam]] == Union[Last[sam]],
> >         Split[Flatten[{Join[First[sam], Last[sam]],
> Rest[Drop[sam, -1]]}]], sam];
> >       Table[Count[newsam, x_ /; Union[x] == {1} && Length[x] == j] >= 1,
> {j, 0, lt}] /.
> >        {True :> 1, False :> 0}]]
> >
> > I repeated the experiment 100,000 times for a sequence of five sites
> (roughly 3 minutes in a slowish machine):
> >
> > In[3]:=
> > Timing[reps = Table[oneExp[5], {100000}]; ]
> > Out[3]=
> > {179.94*Second, Null}
> >
> > and I obtain the following approximations:
> >
> > In[17]:=
> > (Plus @@ #1 & ) /@ Transpose[reps]/100000.
> > Out[17]=
> > {0.0317,0.46995,0.31393,0.15616,0.15603,0.03042}
> >
> > The relative frequency of all 0's is 0.0317, whereas the rel frec of all
> 1's is 0.0342, both estimating the true value of (1/2)^5 = 0.03125. The
2nd,
> 3rd, etc. values are the rel frecs of "at least one run of length 1", "at
> least one run of length 2", etc., respectively. The procedure, I realize,
is
> rather crude, in the sense that the variability of the results seems quite
> high, even though they are within acceptable bounds. I guess it might be
> refined somehow.
> >
> > Tomas Garza
> > Mexico City
> > Original Message:
> > -----------------
> > From: Seth Chandler SChandler at Central.UH.Edu
To: mathgroup at smc.vnet.net
> > Subject: [mg32373] [mg32324] [mg32312] Runs on a Ring
> >
> >
> > This is a combined math and Mathematica problem. Suppose one has a ring
of
> n
> > sites. Each site is populated by a zero or a one, each with random
> > probability one half. What are the odds that in a ring of size n there
is
> at
> > least one run of ones (or, equivalently, zeros) of length t? The problem
> is
> > solved for lists of site n. See http://mathworld.wolfram.com/Run.html
for
> an
> > excellent discussion, but I have not been able to find a solution for
> rings.
> >
> > I have been able to solve the problem inelegantly for runs of length 3
by
> > using the package RSolve to solve some coupled difference equations
> > generated largely from observation.
> >
> > --------------------------------------------------------------------
> > mail2web - Check your email from the web at
> > http://mail2web.com/ .
> >
> >
> >
>

```

• Prev by Date: RE: Mysterious 3-way Collision of Polygons
• Next by Date: Re: Taylor Series Expansions
• Previous by thread: Re: RE: Runs on a Ring
• Next by thread: Re: Runs on a Ring