Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2002
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2002

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

Search the Archive

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