Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

RE: Runs on a Ring

• To: mathgroup at smc.vnet.net
• Subject: [mg32324] RE: [mg32312] Runs on a Ring
• From: "tgarza01 at prodigy.net.mx" <tgarza01 at prodigy.net.mx>
• Date: Tue, 15 Jan 2002 02:30:00 -0500 (EST)
• Reply-to: tgarza01 at prodigy.net.mx
• Sender: owner-wri-mathgroup at wolfram.com

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: [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/ .

• Follow-Ups:
  • Re: RE: Runs on a Ring
    • From: "Philippe Dumas" <dumasphi@noos.fr>