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\) <math> <mrow> <mrow> <mi>probs</mi> <mo>⁡</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>⁡</mo> <mrow> <mo>[</mo> <mrow> <mrow> <mi>Normal</mi> <mo>⁡</mo> <mrow> <mo>[</mo> <mrow> <mi>Series</mi> <mo>⁡</mo> <mrow> <mo>[</mo> <mrow> <mfrac> <mrow> <msup> <mi>z</mi> <mi>t</mi> </msup> <mo>⁢</mo> <mstyle> <mspace width='0.3em' height='0.3ex'/> </mstyle> <mo>⁢</mo> <mrow> <mo>(</mo> <mrow> <mn>1</mn> <mo>+</mo> <mrow> <mi>z</mi> <mo>⁢</mo> <mstyle> <mspace width='0.3em' height='0.3ex'/> </mstyle> <mo>⁢</mo> <mrow> <mo>(</mo> <mrow> <mrow> <mn>3</mn> <mo>⁢</mo> <mstyle> <mspace width='0.3em' height='0.3ex'/> </mstyle> <mo>⁢</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>⁢</mo> <mstyle> <mspace width='0.3em' height='0.3ex'/> </mstyle> <mo>⁢</mo> <mi>z</mi> </mrow> </mrow> <mo>)</mo> </mrow> <mo>⁢</mo> <mstyle> <mspace width='0.3em' height='0.3ex'/> </mstyle> <mo>⁢</mo> <mrow> <mo>(</mo> <mrow> <mi>t</mi> <mo>-</mo> <mrow> <mi>t</mi> <mo>⁢</mo> <mstyle> <mspace width='0.3em' height='0.3ex'/> </mstyle> <mo>⁢</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>⁢</mo> <mstyle> <mspace width='0.3em' height='0.3ex'/> </mstyle> <mo>⁢</mo> <mrow> <mo>(</mo> <mrow> <mrow> <mo>-</mo> <mn>1</mn> </mrow> <mo>+</mo> <mrow> <mn>2</mn> <mo>⁢</mo> <mstyle> <mspace width='0.3em' height='0.3ex'/> </mstyle> <mo>⁢</mo> <mi>z</mi> </mrow> </mrow> <mo>)</mo> </mrow> <mo>⁢</mo> <mstyle> <mspace width='0.3em' height='0.3ex'/> </mstyle> <mo>⁢</mo> <mrow> <mo>(</mo> <mrow> <mn>1</mn> <mo>+</mo> <mrow> <mi>z</mi> <mo>⁢</mo> <mstyle> <mspace width='0.3em' height='0.3ex'/> </mstyle> <mo>⁢</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>⁡</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> </math>