Re: Runs on a Ring

• To: mathgroup at smc.vnet.net
• Subject: [mg32411] Re: Runs on a Ring
• From: "Seth Chandler" <SChandler at Central.UH.Edu>
• Date: Sat, 19 Jan 2002 01:16:57 -0500 (EST)
• Organization: University of Houston
• References: <a20m2l\$4ft\$1@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

```Thanks for taking a look at the problem. I believe I now have an analytic
solution to the runs on a ring problem. If there are n sites on a ring with
two colors selected at random, the probability of achieving a run of length
t may be determined by the following Mathematica expression. I am including
it in input form and MathML form. I was greatly aided in my research both by
the RSolve package and the beta of the new Combinatorica package at
http://www.cs.uiowa.edu/~sriram/Combinatorica/.

\!\(probs[t_,
n_] := \(CoefficientList[Normal[Series[\(z\^t\ \((1 + z\ \((3\ \
\((\(-1\) + z)\) + \((1 - 2\ z)\)\ \((t - t\ z +
z\^t)\))\))\)\)\/\(\((\(-1\) \
+ z)\)\ \((\(-1\) + 2\ z)\)\ \((1 + z\ \((\(-2\) + z\^t)\))\)\), {z, 0,
n}]], \
z]\)[\([\(-1\)]\)]\/2\^n\)

[itex]
<mrow>
<mrow>
<mi>probs</mi>
<mo>&af;</mo>
<mrow>
<mo>[</mo>
<mrow>
<mi>t_</mi>
<mo>,</mo>
<mi>n_</mi>
</mrow>
<mo>]</mo>
</mrow>
</mrow>
<mo>:=</mo>
<mfrac>
<mrow>
<mrow>
<mi>CoefficientList</mi>
<mo>&af;</mo>
<mrow>
<mo>[</mo>
<mrow>
<mrow>
<mi>Normal</mi>
<mo>&af;</mo>
<mrow>
<mo>[</mo>
<mrow>
<mi>Series</mi>
<mo>&af;</mo>
<mrow>
<mo>[</mo>
<mrow>
<mfrac>
<mrow>
<msup>
<mi>z</mi>
<mi>t</mi>
</msup>
<mo>&it;</mo>
<mstyle>
<mspace width='0.3em' height='0.3ex'/>
</mstyle>
<mo>&it;</mo>
<mrow>
<mo>(</mo>
<mrow>
<mn>1</mn>
<mo>+</mo>
<mrow>
<mi>z</mi>
<mo>&it;</mo>
<mstyle>
<mspace width='0.3em' height='0.3ex'/>
</mstyle>
<mo>&it;</mo>
<mrow>
<mo>(</mo>
<mrow>
<mrow>
<mn>3</mn>
<mo>&it;</mo>
<mstyle>
<mspace width='0.3em'
height='0.3ex'/>
</mstyle>
<mo>&it;</mo>
<mrow>
<mo>(</mo>
<mrow>
<mrow>
<mo>-</mo>
<mn>1</mn>
</mrow>
<mo>+</mo>
<mi>z</mi>
</mrow>
<mo>)</mo>
</mrow>
</mrow>
<mo>+</mo>
<mrow>
<mrow>
<mo>(</mo>
<mrow>
<mn>1</mn>
<mo>-</mo>
<mrow>
<mn>2</mn>
<mo>&it;</mo>
<mstyle>
<mspace width='0.3em'
height='0.3ex'/>
</mstyle>
<mo>&it;</mo>
<mi>z</mi>
</mrow>
</mrow>
<mo>)</mo>
</mrow>
<mo>&it;</mo>
<mstyle>
<mspace width='0.3em'
height='0.3ex'/>
</mstyle>
<mo>&it;</mo>
<mrow>
<mo>(</mo>
<mrow>
<mi>t</mi>
<mo>-</mo>
<mrow>
<mi>t</mi>
<mo>&it;</mo>
<mstyle>
<mspace width='0.3em'
height='0.3ex'/>
</mstyle>
<mo>&it;</mo>
<mi>z</mi>
</mrow>
<mo>+</mo>
<msup>
<mi>z</mi>
<mi>t</mi>
</msup>
</mrow>
<mo>)</mo>
</mrow>
</mrow>
</mrow>
<mo>)</mo>
</mrow>
</mrow>
</mrow>
<mo>)</mo>
</mrow>
</mrow>
<mrow>
<mrow>
<mo>(</mo>
<mrow>
<mrow>
<mo>-</mo>
<mn>1</mn>
</mrow>
<mo>+</mo>
<mi>z</mi>
</mrow>
<mo>)</mo>
</mrow>
<mo>&it;</mo>
<mstyle>
<mspace width='0.3em' height='0.3ex'/>
</mstyle>
<mo>&it;</mo>
<mrow>
<mo>(</mo>
<mrow>
<mrow>
<mo>-</mo>
<mn>1</mn>
</mrow>
<mo>+</mo>
<mrow>
<mn>2</mn>
<mo>&it;</mo>
<mstyle>
<mspace width='0.3em' height='0.3ex'/>
</mstyle>
<mo>&it;</mo>
<mi>z</mi>
</mrow>
</mrow>
<mo>)</mo>
</mrow>
<mo>&it;</mo>
<mstyle>
<mspace width='0.3em' height='0.3ex'/>
</mstyle>
<mo>&it;</mo>
<mrow>
<mo>(</mo>
<mrow>
<mn>1</mn>
<mo>+</mo>
<mrow>
<mi>z</mi>
<mo>&it;</mo>
<mstyle>
<mspace width='0.3em' height='0.3ex'/>
</mstyle>
<mo>&it;</mo>
<mrow>
<mo>(</mo>
<mrow>
<mrow>
<mo>-</mo>
<mn>2</mn>
</mrow>
<mo>+</mo>
<msup>
<mi>z</mi>
<mi>t</mi>
</msup>
</mrow>
<mo>)</mo>
</mrow>
</mrow>
</mrow>
<mo>)</mo>
</mrow>
</mrow>
</mfrac>
<mo>,</mo>
<mrow>
<mo>{</mo>
<mrow>
<mi>z</mi>
<mo>,</mo>
<mn>0</mn>
<mo>,</mo>
<mi>n</mi>
</mrow>
<mo>}</mo>
</mrow>
</mrow>
<mo>]</mo>
</mrow>
</mrow>
<mo>]</mo>
</mrow>
</mrow>
<mo>,</mo>
<mi>z</mi>
</mrow>
<mo>]</mo>
</mrow>
</mrow>
<mo>&af;</mo>
<mrow>
<mo>[</mo>
<mrow>
<mo>[</mo>
<mrow>
<mo>-</mo>
<mn>1</mn>
</mrow>
<mo>]</mo>
</mrow>
<mo>]</mo>
</mrow>
</mrow>
<msup>
<mn>2</mn>
<mi>n</mi>
</msup>
</mfrac>
</mrow>
[/itex]

```

• Prev by Date: Re: Mysterious 3-way Collision of Polygons
• Next by Date: Re: When does x/x not equal 1?
• Previous by thread: Re: RE: Runs on a Ring