Re: RE: Runs on a Ring
- To: mathgroup at smc.vnet.net
- Subject: [mg32371] Re: [mg32324] RE: [mg32312] Runs on a Ring
- From: "Philippe Dumas" <dumasphi at noos.fr>
- Date: Wed, 16 Jan 2002 03:31:05 -0500 (EST)
- References: <200201150730.CAA04513@smc.vnet.net>
- Reply-to: "Philippe Dumas" <dumasphi at noos.fr>
- Sender: owner-wri-mathgroup at wolfram.com
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
Subject: [mg32371] [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: [mg32371] [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/ .
>
>
>
- References:
- RE: Runs on a Ring
- From: "tgarza01@prodigy.net.mx" <tgarza01@prodigy.net.mx>
- RE: Runs on a Ring