The sum of a "partial" geometric series?

Patrick Lam · science forum beginner Joined: 14 Jun 2006 Posts: 13

Dear all,

I need to find the the sum of a partial geometric series. That is, assuming
the following series sum up to one:

a, a^2, a^3, ......a^N

Among these N terms, I need to randomly select K of them (K < N). How can I
find the expected sum of these K "selected" terms in terms of a, K and N?

To formally express this question,

Given:
a + a^2 + a^3 + ......a^N = 1

Find:

summation j=1 to j=K (B_j*a^j)

where B_j = 1 when the term a^j is randomly selected and B_j = 0 otherwise.

Thanks very much in advance.

Regards,

Patrick

danheyman@yahoo.com · science forum beginner Joined: 18 Jul 2005 Posts: 33

You have to specify how the K items are selected; "randonly" isn't
precise enough. Is K a random variable or fixed? For example, you could
mean the K is a binomial random variable with "success probability" 1/N
and number of trials = N. Or, you could mean K is a given number and
you sample from the N numbers in such a way as to ensure K are chosen.
Without such info, your probelm is indeterminate.

Dan Heyman

Patrick Lam wrote:

Patrick Lam · science forum beginner Joined: 14 Jun 2006 Posts: 13

Hi,

Thanks for your hints.

Actually, K is a determined constant that is smaller than N (which is yet
another constant). Therefore, among the N terms a, a^2, a^3, ......a^N, K
are chosen and I need to find the expected sum of the K chosen terms in
terms of a, N and K.

Anything else I need to specify?

Thanks again in advance.

Regards,

Patrick

<danheyman@yahoo.com> wrote in message
news:1150327949.313150.80980@u72g2000cwu.googlegroups.com...

amit · science forum beginner Joined: 15 Jun 2006 Posts: 1

hi,
you want to find expected value of Y, where Y is summation j=1 to j=N
(B_j*a^j)
where B_j = 1 when the term a^j is selected and B_j = 0
otherwise.(note j will run from 1 to N and not from 1 to K ,otherwise
you are always selecting first K terms only).
since we are selecting K out of N, each term will have probabilty K/N
to occur in our sample, so P(B_j = 1) = K/N for all j.
now E(Y) = E(summation j=1 to j=N (B_j*a^j)) = summation j=1 to j=N
E(B_j*a^j)
= summation j=1 to j=N a^j*E(B_j) = summation j=1 to j=N a^j*P(B_j=1)
= P(B_j=1)*(summation j=1 to j=N a^j) = K/N*1 = K/N.
hope it is clear.
amit

Patrick Lam · science forum beginner Joined: 14 Jun 2006 Posts: 13

Hi Amit,

Thanks very much for the clear derivation.

I actually had thought about that too (although deriving from another
angle). But then I wondered why the expected sum is independent of the
series at all. For example, another series:

a + a + a + a + a ... + a = 1

will produce the same expected sum I wanted. It was kind of anti-intuitive
to me. It still is, but I think your derivation is correct.

Regards,

Patrick

"amit" <amit.kothiyal@cranessoftware.com> wrote in message
news:1150361743.782354.327050@g10g2000cwb.googlegroups.com...

danheyman@yahoo.com · science forum beginner Joined: 18 Jul 2005 Posts: 33

Amit's solution is not correct. He made the number of selected items a
binomial random variable with mean K, but the number selected will vary
from 0 to N according to the binomial distribution.
You have to specify HOW the elements are selected. For example, you
could select the first K, or the last K, or the middle K, etc. I assume
you want a probabilisitc selection, so select the term a^1 with
probability K/N. If it is selected, select the term a^2 with
probability [K-1]/[N-1]; otherwise, select it with probability K/[N-1].
Proceed in this way until K are selected. This will lead to a recursive
equation for the sum you want.
Dan Heyman

Patrick Lam wrote:

Patrick Lam · science forum beginner Joined: 14 Jun 2006 Posts: 13

Hi,

This is a very good point. Thanks very much.

Regards,

Patrick

<danheyman@yahoo.com> wrote in message
news:1150414156.123320.239220@h76g2000cwa.googlegroups.com...

amit · science forum beginner Joined: 19 Jun 2006 Posts: 1

hi,
I don't see any any problem with my derivation, there are nCk(
=fact(n)/(fact(k)*fact(n-k)) )
no of ways in which you can choose k terms out of n terms, and since
you are choosing randomly each term have same probability of
appearance, there are nCk samples of k terms and I think it's clear the
way problem is stated that random selection means here that you pick
one out of these nCk things such that probability of choosing any is
1/nCk
now fix any term it will occur in (n-1)C(k-1) numbers of sample so
probability of its occurence is (n-1)C(k-1)/nCk = k/n.
appart from that I used linearity of expectation i.e E(X+Y) = E(X)+E(Y)
, X and Y are two random variables they need not be indepndent, above
is true even if you have more then two r.v (which can be proved easily
by induction).
derivation i gave holds as long as probability of any term to occur in
choosen sample is k/n, if this condition is met then it doesn't matter
how you are choosing,since apart from it my derivation used only
linearity of expectation, which holds quite generally.
I think in any sampling schemes this condition will be met(provided
any term is as likely to be choosen as any other term).
Patric i don't see any thing surprising in your example, my derivationI
does not used any structure on the series replace a^i by a(i) , which
is the i'th term of the series, and it still
works, you have just taken a(i) to be constant a and verify for this
special case that expectation is just k/n.
cheers,
amit

Patrick Lam wrote:

danheyman@yahoo.com · science forum beginner Joined: 18 Jul 2005 Posts: 33

What's wrong with your drivation is that the OP said that K is a fixed
number, and you made it a random variable with mean K. Random selection
MAY mean that each of N items is picked with probability K/N, but it
MAY ALSO mean that after n items have been looked at and k of them
picked, each of the reamaining N-n items is picked with probabilty
[K-k]/[N-n]. The latter will select exactly K, and a priori, each of
the original items has the same chance of being selected.
Dan Heyman

amit wrote:

amit · science forum beginner Joined: 20 Jun 2006 Posts: 1

hi,
I have assumed K to be fixed number and not a random variable, and
sampling scheme I used in my derivation is srswor(simple random
sampling without replacement), that is first you pick one term
randomely(any term is equally likely to occur),then you pick another
and so on untill you have K terms, but as i say earlier whatever
sampling scheme will give K/N as probability of any term to occur in
sample, will have the expected sum as K/N, and any sampling scheme
which does not distinguish between two terms,and in which no term is
repeated will have the desired probability(this second assertion is my
guess)
amit.
danheyman@yahoo.com wrote:

danheyman@yahoo.com · science forum beginner Joined: 18 Jul 2005 Posts: 33

It sems I read your post incorectly; I focused on the assertion that
each term is picked with probability K/N and (incorectly) thought you
meant Bernoulli sampling. The sampling scheme I proposed looks like
srswor, and indeed one can show that each term has probability K/N of
being in the sum, so your conclusion is valid for this scheme.
Dan Heyman

amit wrote:

Google