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

**References**:**RE: Runs on a Ring***From:*"tgarza01@prodigy.net.mx" <tgarza01@prodigy.net.mx>