Allstaters,
I posted the following (restated) problem a few weeks ago. I received
the following answers in plain text. I also received detailed solutions
in pdf format from Berwin Terlac and Mark Muldoon. It would probably
be breaking the "plain text only" rule for Allstat to distribute these
to the list. However, I would be pleased to send copies to anyone who
requests them.
My thanks to all who responded.
Allan
---------------------------------------------------------------------------
Please accept my apologies for a second posting. My earlier attempt
revealed some serious ambiguities in my formulation of the problem.
I wish to express my thanks to all those who tried to grapple with
my inadequate specification of the problem the first time.
Let me try again. Suppose that I run n iid Bernoulli processes
synchronously and in parallel. I define this as a meta-process.
This is run until meta-success is achieved, where meta-success
is defined as having achieved a success on EACH of the individual
processes. What is the number of trials (of the meta-process)
required to achieve meta-success?
Note 1. This is asking for the expectation of the maximum (no. of
trials) for n iid Bernoulli processes.
Note 2. Consider n=2 and p=0.5 as an example.
p(1)=1/4
p(2)=5/16
p(3)=13/64
p(4)=29/256
and so on.
Note 3. I note that I can get the probability for requiring exactly k
trials p(k) from the corresponding cdf by differencing thus:
p(1)=p**n
cdf(k)=(1-q**k)**n
p(k)=cdf(k)-cdf(k-1)
Thus I require the sum from k=1 to k=infinity of k*p(k) to
get the expectation that I require.
Allan
---------------------------------------------------------------------------
Having noticed your original statement yesterday, I had a quick
go and thought I made some progress, but I don't suppose I'll be
able to get too far in the time I have available.
I think I can solve the problem OK in principle, but some of the
details need to be tidied - and could of course be messy
algebraically.
Here goes. I'm sure the basis for the best approach lies along
the lines in your "Note 3", where you get the cdf. (That's just
the usual form for the cdf of the maximum Y of a set of iid rvs
X_1, X_2, ..., X_n.)
Where I differ from you is how to handle the cdf of Y. You
difference the cdf to get the pf. I think it might be easier to
work with the survivor function S(k) = 1 - F_Y(k). [I haven't
quite sorted out in my mind whether we should be working with the
survivor function as Pr(Y>=y) or Pr (Y>y): I usually only work
with survivor functions for continuous rvs, where of course it
doesn't matter which you take.]
The simplification is that E(Y), which you correctly write as
sum from k=1 to k=infinity of k*p(k),
can also be written as
sum from k=1 to k=infinity of S(k),
as long as S(k) is appropriately defined. (See my [...] above.)
Best wishes
Eryl Bassett
----------------------------------------------------------------------------
Anyway I thought it useful to point out that the expectation of a random
variable can be written as the sum/integral of the survival function. So
here you want sum( 1- (1-q^k)^n) over k=1..infinity. Plugging this into
the symbolic processing package Maple indicates that there's no closed
form for n>1. However, I did notice that you could expand (1-p^k)^n using
the bionomial theorem, and then swap the order of summation. The sums over
k, now can be done in closed form since they're geometric series and
you're left with a finite sum from 1..n.
Let me know if you get any other interesting answers.
Simon Bond.
-----------------------------------------------------------------------------
If not, and I haven't misunderstood the problem,
I reckon the following holds (warning: I haven't
done any checking in books; a small simulation
(with n = 2, 4, 8; p = 1/4) gave
results which were close enough for the mean):
Let M be the overall number of trials until you
get a (first) success in each of the n independent
Bernoulli sequences (success probability p), and
let q = 1 - p.
Then
E(M) = sum{r = 1 to n} [ (n choose r) (-1)^(r-1)/(1-q^r)].
For good measure (so you can get the variance)
E[M(M+1)] = 2 sum{r = 1 to n} [ (n choose r) (-1)^(r-1)/((1-q^r))^2]
These sums give the correct expressions when n = 1
(i.e. geometric).
I hope that you can interpret the notation!
Let me know if you want further details.
I hope this helps...
Regards,
Giles Thomas
------------------------------------------------------------------------------
--
Dr. Allan White, Statistical Advisory Service, University of Birmingham
Tel. 0121-414 4750 or 44750 (internal), Email [log in to unmask]
|