Re: a combinatorics proof needed
From: Fred the Wonder Worm (ftww_at_maths.usyd.edu.au)
Date: 10/08/04
- Next message: Felix Goldberg: "Re: Algorithmic complexity of a graph"
- Previous message: Dave Wagner: "Re: a combinatorics proof needed"
- In reply to: Rob Pratt: "Re: a combinatorics proof needed"
- Next in thread: Chakravarthi: "Re: a combinatorics proof needed"
- Messages sorted by: [ date ] [ thread ]
Date: 8 Oct 2004 07:43:47 GMT
In article <ck43u6$1m9$1@license1.unx.sas.com>,
Rob Pratt <Rob.Pratt@sas.com> wrote:
>"Fred the Wonder Worm" <ftww@maths.usyd.edu.au> wrote in message
>news:ck2ls2$da6$1@spacebar.ucc.usyd.edu.au...
>> In article <ba1b8b10.0410042146.22fc53d3@posting.google.com>,
>> Chakravarthi <pschax@gmail.com> wrote:
>>>
>>> If we take a random binary sequence of length 'n' how
>>> to prove that the expected number of runs of zeroes
>>> 0000...0 (or 1s) of length 'i' is (n-i+3)/2^(i+2).
[...]
>> The first point is that your formula does not work for i = n,
>> but I assume you are aware of this. Assuming that we have
>> 1 <= i < n, and that we are interested in zeroes. Let E(n,i)
>> be the expected number of runs of zeroes of exact length i in
>> a random bit sequence.
>
> [rest of solution snipped]
>
> Here's a much shorter solution using a powerful property: the
> linear of expectation.
>
> For k = 1 to n - i + 1, define random variable R_k = 1 if an i-run
> starts at position k, 0 otherwise.
>
> Let E(n,i) be defined as above, and denote the expected value of
> R_k by E{R_k}. (By the way, the expected value of a Bernoulli
> random variable is just the probability that the variable is 1.)
> Now the total number of i-runs is sum [k = 1 to n - i + 1] R_k,
> and so
>
> E(n,i) = E{sum [k = 1 to n - i + 1] R_k}
> = sum [k = 1 to n - i + 1] E{R_k}
> = (n - i) E{R_1} + E{R_n}
> = (n - i) (1/2)^(i+1) + (1/2)^i
> = (n - i + 2) / 2^(i+1),
>
> which differs from the original poster's formula but seems to be
> correct. As a check, note that my formula yields E(n,n) = 1/2^n,
> as expected.
This seems to be the only case where it returns the correct
answer. For example, consider the simple case where n=2,i=1:
runs
00 0
01 1
10 1
11 0
For an expected value of 1/2, whereas your formula gives 3/4.
I'm guessing this discrepancy arises because you are considering
the '00' case to have a run of 1 zero starting at the second
position, but (based on the formula) it seems clear this is not
the original poster's intent.
Modifying your argument based on this does yield a much simpler
approach:
E(n,i) = E{sum [k = 1 to n - i + 1] R_k}
= sum [k = 1 to n - i + 1] E{R_k}
= E{R_1} + (n-i-1)*E{R_2} + E{R_(n-i+1)}
= 1/2^(i+1) + (n-i-1)/2^(i+2) + 1/2^(i+1)
= (n - i + 3) / 2^(i+2)
[ i.e., the expected value E{R_1} is the probability that the
sequence starts with an i-run, which is the probability that it
starts with i 0s followed by a 1, which is 1/2^(i+1). Similarly
for E{R_(n-i+1)}. The other E{R_j} are all equal to E{R_2},
which is the probability of a 1, i 0s and another 1 appearing
in the appropriate positions, which is 1/2^(i+2). ]
This formula breaks down when i = n, but we already knew that.
Thanks for pointing this approach out.
Cheers,
Geoff.
-----------------------------------------------------------------------------
Geoff Bailey (Fred the Wonder Worm) | Programmer by trade --
ftww@maths.usyd.edu.au | Gameplayer by vocation.
-----------------------------------------------------------------------------
- Next message: Felix Goldberg: "Re: Algorithmic complexity of a graph"
- Previous message: Dave Wagner: "Re: a combinatorics proof needed"
- In reply to: Rob Pratt: "Re: a combinatorics proof needed"
- Next in thread: Chakravarthi: "Re: a combinatorics proof needed"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
