Re: Re: Sequence of Bernoulli RVs

*To*: mathgroup at smc.vnet.net*Subject*: [mg73018] Re: [mg72998] Re: Sequence of Bernoulli RVs*From*: Andrzej Kozlowski <akoz at mimuw.edu.pl>*Date*: Mon, 29 Jan 2007 04:27:36 -0500 (EST)*References*: <epf9es$c1o$1@smc.vnet.net> <200701280559.AAA28840@smc.vnet.net>

On 28 Jan 2007, at 06:59, Ray Koopman wrote: > Virgil Stokes wrote: >> The following code will get the expected number of >> "runs" (sequence of >> equal values) for a sequence of Bernoulli RVs in terms of p, which is >> the probability of the value 1, and of course, (1-p), the >> probability of 0. >> >> n=3 >> l1 = Tuples[{(1-p),p},n]; (* generate Bernoulli sequence of length >> n *) >> xx = Table[Split[l1[[k]]],{k,1,Length[l1]}]; (* list of runs *) >> l2 = Map[Length,Map[Split,xx]]; (* lengths of each run *) >> tt = Table[Times@@l1[[k]],{k,1,Length[l2]}]; (* probabilities for >> each >> run *) >> expectedruns = Inner[Times,tt,l2]//FullSimplify (* mean of a >> function >> of a Discrete RV *) >> >> It may not be very obvious that this is correct. Please try it over a >> range of values of n (n=1,2,...) if you are in doubt. The expected >> value for such a sequence is given by >> >> E[number of runs] = 1 + 2(n-1)(p-1)p >> >> Finally, my question --- Is it possible to derive this equation (in >> terms of p and n) using Mathematica? >> >> --V. Stokes > > I don't see a role for Mathematica to play here. If an (n+1)st bit > is appended to an n-bit sequence, the probability that it creates > a new run is 2p(1-p), and the probability that it extends the old > terminal run is 1 - 2p(1-p). Hence > > ExpectedRuns[n+1] = (ExpectedRuns[n] + 1) * 2p(1-p) + > ExpectedRuns[n] * (1 - 2p(1-p)) > > = ExpectedRuns[n] + 2p(1-p). > Since > > ExpectedRuns[1] = 1, > > it follows immediately that > > ExpectedRuns[n] = 1 + 2(n-1)p(1-p). > > What would you have Mathematica do? > It is possible to make use of Mathematica to derive the equation, provided one is (or choses to be) less clever than Ray ;-) The way to do it is by first trying to find the formula for exactly k runs in a sequence of n trials. We will start with the second throw and think of a "success" when a new run is created and a failure when it is not created. So, as above, the probability of "success" is 2 p (1-p) and of "failure" 1- 2 p (1-p) Thus the probability of k "successes" (starting with the second trial) Binomial[n - 1, k]*(2*p*(1 - p))^k*(1 - 2*p*(1 - p))^(-k + n - 1) and the expected value is: Assuming[n > 0 && p > 0, Simplify[Sum[k*Binomial[n - 1, k]*(2*p*(1 - p))^k* (1 - 2*p*(1 - p))^(-k + n - 1), {k, 0, n - 1}]]] + 1 1 - 2*(n - 1)*(p - 1)*p (we have to add one because the number of runs is 1 more than the number of successes, since we start counting form the second trial). Andrzej Kozlowski

**References**:**Re: Sequence of Bernoulli RVs***From:*"Ray Koopman" <koopman@sfu.ca>