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

Posted: Wed Jun 14, 2006 5:42 pm Post subject:
The sum of a "partial" geometric series?



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 

Back to top 


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

Posted: Wed Jun 14, 2006 11:32 pm Post subject:
Re: The sum of a "partial" geometric series?



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:
Quote:  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 


Back to top 


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

Posted: Thu Jun 15, 2006 1:34 am Post subject:
Re: The sum of a "partial" geometric series?



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...
Quote:  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:
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



Back to top 


amit1 science forum beginner
Joined: 15 Jun 2006
Posts: 1

Posted: Thu Jun 15, 2006 8:55 am Post subject:
Re: The sum of a "partial" geometric series?



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 wrote:
Quote:  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 


Back to top 


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

Posted: Thu Jun 15, 2006 10:35 am Post subject:
Re: The sum of a "partial" geometric series?



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 antiintuitive
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...
Quote:  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 wrote:
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



Back to top 


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

Posted: Thu Jun 15, 2006 11:29 pm Post subject:
Re: The sum of a "partial" geometric series?



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 [K1]/[N1]; otherwise, select it with probability K/[N1].
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:
Quote:  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 antiintuitive
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...
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 wrote:
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



Back to top 


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

Posted: Fri Jun 16, 2006 2:12 pm Post subject:
Re: The sum of a "partial" geometric series?



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...
Quote:  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 [K1]/[N1]; otherwise, select it with probability K/[N1].
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:
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
antiintuitive
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...
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 wrote:
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



Back to top 


amit2 science forum beginner
Joined: 19 Jun 2006
Posts: 1

Posted: Mon Jun 19, 2006 1:01 pm Post subject:
Re: The sum of a "partial" geometric series?



hi,
I don't see any any problem with my derivation, there are nCk(
=fact(n)/(fact(k)*fact(nk)) )
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 (n1)C(k1) numbers of sample so
probability of its occurence is (n1)C(k1)/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:
Quote:  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'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 [K1]/[N1]; otherwise, select it with probability K/[N1].
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:
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
antiintuitive
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...
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 wrote:
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



Back to top 


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

Posted: Mon Jun 19, 2006 7:12 pm Post subject:
Re: The sum of a "partial" geometric series?



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 Nn items is picked with probabilty
[Kk]/[Nn]. 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:
Quote:  hi,
I don't see any any problem with my derivation, there are nCk(
=fact(n)/(fact(k)*fact(nk)) )
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 (n1)C(k1) numbers of sample so
probability of its occurence is (n1)C(k1)/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:
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'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 [K1]/[N1]; otherwise, select it with probability K/[N1].
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:
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
antiintuitive
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...
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 wrote:
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



Back to top 


amit3 science forum beginner
Joined: 20 Jun 2006
Posts: 1

Posted: Tue Jun 20, 2006 4:08 am Post subject:
Re: The sum of a "partial" geometric series?



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:
Quote:  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 Nn items is picked with probabilty
[Kk]/[Nn]. 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:
hi,
I don't see any any problem with my derivation, there are nCk(
=fact(n)/(fact(k)*fact(nk)) )
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 (n1)C(k1) numbers of sample so
probability of its occurence is (n1)C(k1)/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:
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'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 [K1]/[N1]; otherwise, select it with probability K/[N1].
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:
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
antiintuitive
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...
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 wrote:
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



Back to top 


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

Posted: Fri Jun 23, 2006 8:41 am Post subject:
Re: The sum of a "partial" geometric series?



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:
Quote:  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:
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 Nn items is picked with probabilty
[Kk]/[Nn]. 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:
hi,
I don't see any any problem with my derivation, there are nCk(
=fact(n)/(fact(k)*fact(nk)) )
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 (n1)C(k1) numbers of sample so
probability of its occurence is (n1)C(k1)/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:
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'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 [K1]/[N1]; otherwise, select it with probability K/[N1].
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:
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
antiintuitive
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...
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 wrote:
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



Back to top 


Google


Back to top 



The time now is Fri Sep 21, 2018 4:19 pm  All times are GMT

