Prev: the Lonely runner conjecture
Next: ==P Versus NP Solution Claimed==
From: Ray Vickson on 10 May 2010 16:06
On May 10, 11:40 am, atrovantes <eba...(a)gmail.com> wrote:
> > On May 10, 6:18 am, atrovantes <eba...(a)gmail.com>
> > wrote:
> > > Hi,
> > > does anyone know any results about weighted sums of
> > Bernoullis?
>
> > > A simple example follows. Let X_n be i.i.d.
> > Bernoulli random variables. What's the distribution
> > of
> > > \sum_{k=1}^N X_k k ?
>
> > > Or if not the distribution maybe some other
> > results... Non-trivial of course (e.g. I can find the
> > mean myself).
>
> > > Thanx in advance.
>
> > For the specific case of S = X_1 + 2*X_2 + 3*X_3 +
> > ... + N*X_N the
> > moment-generating function is G(z) = (q + p*z)*(q +
> > p*z^2)*(q
> > +p*z^3)*...*(q+p*z^N), where q = 1-p. For small N one
> > can expand out
> > the product and collect coefficients of z^j to find
> > the probabilities
> > P{S = j}, but for large N it is probably a hopeless
> > task.
>
> That's what I was thinking, but you put it in a beautiful and clearer form using the moment-generating function. Thanx.
>
> So now the question is (still for the specific case of S^N = X_1 + 2*X_2 + ... + N*X_N) how does G^N(z) = (q + p*z)*(q + p*z^2)*...*(q + p*z^N) behaves.
>
> Well, there is a pattern. We can write G^N(z) as follows:
> G^N(z) = p^N * (b + z)*(b + z^2)*...*(b + z^N), where b=q/p.
>
> And we have:
> b + z
> (b + z)*(b + z^2) = b^2 + b*z + b*z^2 + z^3
> (b^2 + b*z + b*z^2 + z^3)*(b + z^3) = b^3 + b^2*z + b^2*z^2 + (b+b^2)z^3 + b*z^4 + b*z^5 + z^6
> ..
> [it looks better on paper.]
>
> I have a headache now, but I think something will come out of this.
>
>
>
> > However, finding some of the moments is relatively
> > easy. For any sum
> > of the form T = sum{i=1}^N a_i*X_i with constants a_i
> > and iid
> > Bernoulli X_j, the mean = sum_{i} a_i * p = p*sum
> > a_i, while for any
> > _independent_ terms, Var(sum) = sum (var), hence
> > Var(T) = sum_{i}
> > (a_i)^2 *p*q = p*q*sum (a_i)^2. For the special case
> > of T = S (with
> > a_i = i) you can use G(z) to find some of the higher
> > moments, while
> > for the general case of S you can use the Laplace
> > transform.
>
> > R.G. Vickson
>
>

For the specific case of S = X_1 + 2*X_2 + ... + N*X_N one can use a
recursive method to get the generating function G_N(z) = prod[(q
+p*z^j,j=1..N] and the probabilities. Say we have G_k(z); then G_{k+1}
(z) = G_k(z)*[q+p*z^(k+1)], so if G_k(z) = sum_{j=0}^n(k) c(k,j)*z^j,
the coefficients c(k+1,j) of z^j in G_{k+1}(z) = sum_{j=0..n(k+1)} c(k
+1,j)*z^j are relatively easy to find: n(k+1) = n(k)+k+1 and c(k+1,j)
= q*c(k,j) + p*c(k,j-k-1); here, c(k,j) = P{S_k = j} = 0 if j > n(k)
and c(k,s) = P{S_k = s} = 0 if s < 0. Thus, P{S_{k+1} = j} = q*P{S_k =
j} + p*P{S_k = j-k-1}. This method is practical even for large N.

R.G. Vickson
From: Stephen Montgomery-Smith on 10 May 2010 16:57
atrovantes wrote:
> Hi,
> does anyone know any results about weighted sums of Bernoullis?
>
> A simple example follows. Let X_n be i.i.d. Bernoulli random variables. What's the distribution of
> \sum_{k=1}^N X_k k ?
>
> Or if not the distribution maybe some other results... Non-trivial of course (e.g. I can find the mean myself).
>
> Thanx in advance.


I wrote a paper on this sort of thing:

http://www.math.missouri.edu/~stephen/preprints/tail.html
From: Robert Israel on 10 May 2010 20:46

> atrovantes <ebaerr(a)gmail.com> writes:
>
> > Hi,
> > does anyone know any results about weighted sums of Bernoullis?
> >
> > A simple example follows. Let X_n be i.i.d. Bernoulli random variables.
> > What's the distribution of
> > \sum_{k=1}^N X_k k ?
> >
> > Or if not the distribution maybe some other results... Non-trivial of
> > course (e.g. I can find the mean myself).
> >
> > Thanx in advance.
>
> Let S_N = sum_{k=1}^N X_k k. P(S_N = m) = f_N(m)/2^N where
> f_N(m) is the number of partitions of m into parts that are all <= N.

Distinct parts, that is.

> This sort of thing has been well studied by number theorists, I think.
--
Robert Israel israel(a)math.MyUniversitysInitials.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia Vancouver, BC, Canada
From: atrovantes on 10 May 2010 22:17
>
> > atrovantes <ebaerr(a)gmail.com> writes:
> >
> > > Hi,
> > > does anyone know any results about weighted sums
> of Bernoullis?
> > >
> > > A simple example follows. Let X_n be i.i.d.
> Bernoulli random variables.
> > > What's the distribution of
> > > \sum_{k=1}^N X_k k ?
> > >
> > > Or if not the distribution maybe some other
> results... Non-trivial of
> > > course (e.g. I can find the mean myself).
> > >
> > > Thanx in advance.
> >
> > Let S_N = sum_{k=1}^N X_k k. P(S_N = m) =
> f_N(m)/2^N where
> > f_N(m) is the number of partitions of m into parts
> that are all <= N.
>
> Distinct parts, that is.
Ok, that's interesting too. Now that you've mentioned the result it's not difficult to find a proof by considering how the sum is formed for successively larger values of N.

However, the result only holds for Bernoullis with corresponding to probability 1/2. Of course the proof gives insight about the general case.

>
> > This sort of thing has been well studied by number
> theorists, I think.
> --
> Robert Israel
> israel(a)math.MyUniversitysInitials.ca
> Department of Mathematics
> http://www.math.ubc.ca/~israel
> University of British Columbia Vancouver,
> BC, Canada
From: atrovantes on 12 May 2010 09:29
> atrovantes wrote:
> > Hi,
> > does anyone know any results about weighted sums of
> Bernoullis?
> >
> > A simple example follows. Let X_n be i.i.d.
> Bernoulli random variables. What's the distribution
> of
> > \sum_{k=1}^N X_k k ?
> >
> > Or if not the distribution maybe some other
> results... Non-trivial of course (e.g. I can find the
> mean myself).
> >
> > Thanx in advance.
>
>
> I wrote a paper on this sort of thing:
>
> http://www.math.missouri.edu/~stephen/preprints/tail.h
> tml

Thanx for this. Your paper contains some stuff that I'm not familiar with, thus I need to take care of some prerequisites first.

Are you aware of any other work on this subject?
First  |  Prev  |  Next  |  Last
Pages: 1 2 3
Prev: the Lonely runner conjecture
Next: ==P Versus NP Solution Claimed==