MathGroup Archive 2007

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

Search the Archive

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


  • Prev by Date: Re: NDSolve -- initial conditions
  • Next by Date: Re: Problem with base 2 logs and Floor
  • Previous by thread: Re: Sequence of Bernoulli RVs
  • Next by thread: Re: Re: Sequence of Bernoulli RVs