A constrained sum

  • Thread starter wdlang
  • Start date
  • #1
307
0

Main Question or Discussion Point

suppose i have N non-negative integers x_1, x_2, ,,, x_N

the constraint is that their summation is N

now for all the configurations, i.e., all the realizations of x_1, x_2, ,,, x_N

i want to find out the average value of

\sum_i x_i^2

i guess is on the order of unity, i.e., O(1).

i am concerned with the large N limit
 
Last edited:

Answers and Replies

  • #2
mathman
Science Advisor
7,757
414
The average value will be somewhere between 1 and N. It depends on what sort of distribution functions the x_k have.
 
  • #3
525
5
First few numbers are (1, 10/3, 60/10).

It could be solved via a recurrence relation by defining M(k,n) as the number of way of summing to k with n terms and S(k,n) as the sum of x_i^2 over all possible ways, so we have

[tex]M(k,n) = M(k,n-1) + ... + M(0,n-1)[/tex]
[tex]S(k,n) = 0 + S(k,n-1) + 1*M(k-1,n-1) + S(k-1,n-1) + ... + k^2*M(0,n-1) + S(0,n-1)[/tex]

with M(k,1)=1, S(k,1)=k^2, e.g. M(2,2)=3, S(2,2)=10, though I don't know the general solution - perhaps generating functions would help?
 
  • #4
307
0
First few numbers are (1, 10/3, 60/10).

It could be solved via a recurrence relation by defining M(k,n) as the number of way of summing to k with n terms and S(k,n) as the sum of x_i^2 over all possible ways, so we have

[tex]M(k,n) = M(k,n-1) + ... + M(0,n-1)[/tex]
[tex]S(k,n) = 0 + S(k,n-1) + 1*M(k-1,n-1) + S(k-1,n-1) + ... + k^2*M(0,n-1) + S(0,n-1)[/tex]

with M(k,1)=1, S(k,1)=k^2, e.g. M(2,2)=3, S(2,2)=10, though I don't know the general solution - perhaps generating functions would help?
i can solve the problem already

it is actually simple

you just need to find the average value of x_1^2

then the average of the sum of the squares is N times of that

but the average of x_1^2 is simple to find, just a bit combination
 
  • #5
525
5
Oh I see, then it reduces to

[tex]E[x_1^2] = \frac{1*M(n-1,n-1) + 2^2*M(n-2,n-1) + ... + n^2*M(0,n-1)}{M(n,n-1)+...+M(0,n-1)}[/tex]

Did you find an expression for M(k,n)?
 
  • #6
307
0
Oh I see, then it reduces to

[tex]E[x_1^2] = \frac{1*M(n-1,n-1) + 2^2*M(n-2,n-1) + ... + n^2*M(0,n-1)}{M(n,n-1)+...+M(0,n-1)}[/tex]

Did you find an expression for M(k,n)?
it is simple

it is a standard result in combination theory
 
  • #7
525
5
Sorry you've lost me - can you post the details or a link to it please?
 
  • #8
307
0
Sorry you've lost me - can you post the details or a link to it please?
i bet you can find the expression of M in any combinational book
 
  • #9
525
5
i bet you can find the expression of M in any combinational book
I don't have easy access to a library so that's not much help. Regardless, using generating functions M(k,n) would be the coefficient of x^k in (1+x+x^2+...)^n = 1/(1-x)^n, provided k<=n, and the kth derivative of this expression is (n+k-1)!/(n-1)!(1-x)^(n+k) so M(k,n)=n+k-1Cn-1 and of course M(0,n-1)+...+M(n,n-1)=M(n,n). Did you find a simple expression for 1^2*M(n-1,n-1)+...+n^2*M(0,n-1) ?
 
  • #10
307
0
I don't have easy access to a library so that's not much help. Regardless, using generating functions M(k,n) would be the coefficient of x^k in (1+x+x^2+...)^n = 1/(1-x)^n, provided k<=n, and the kth derivative of this expression is (n+k-1)!/(n-1)!(1-x)^(n+k) so M(k,n)=n+k-1Cn-1 and of course M(0,n-1)+...+M(n,n-1)=M(n,n). Did you find a simple expression for 1^2*M(n-1,n-1)+...+n^2*M(0,n-1) ?
you got it

i do not find a simple expression of that but i can prove it is convergent, that is what i want
 

Related Threads for: A constrained sum

Replies
8
Views
1K
Replies
4
Views
3K
Replies
1
Views
2K
Replies
0
Views
2K
  • Last Post
Replies
1
Views
1K
Replies
4
Views
2K
Replies
5
Views
16K
Top