|
[Date Index]
[Thread Index]
[Author Index]
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>
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
Next by thread:
A MathLink question
|
