Sign in to follow this  
Pawel Wembley

max and min of a sum

Recommended Posts

I would appreciate very much your help or direction to solve the problem.

Looks like equation

Q=SUM(ABS(B-Ai))

has got min and max values

with the assumptions

0<B<1

0<=Ai<=1

SUM(A1:AK)=1

and i is a natural number from 1 to K

 

Looks like the Qmax and Qmin depend on B and K only. I failed to find general solution for Qmax and Qmin.

 

I attach the pdf with the problem written in Word Equation instead of Excel manner

Q.pdf

Edited by Pawel Wembley

Share this post


Link to post
Share on other sites
renerpho    9

Hello Pawel.

 

The mimimum [math]Q_{min}=\max(KB-1,0)[/math] is calculated as follows:

 

[math]\sum_{i=1}^{K}|B-A{_i}|\geq 0[/math] is trivial, and reached if all [math]A{_i}[/math] are equal to [math]B[/math].

If [math]KB-1>0[/math] then the minimum is not reached at 0, but at [math]\sum_{i=1}^{K}|B-A{_i}|\stackrel{|x|\geq x}{\geq}\sum_{i=1}^{K}(B-A{_i})\[/math] [math]=KB-\sum_{i=1}^{K}A{_i}\ \stackrel{\sum_{i=1}^{K}A{_i}=1}{=}KB-1[/math]. This minimum value is reached if and only if [math]A{_i}<B \forall i[/math].

In the case [math]KB-1<0[/math], you have [math]B<\frac{1}{K}[/math], so at least one of the [math]A{_i}[/math] is larger than [math]B[/math] (by the Pigeon Principle). Which means that [math]KB-1[/math] can't be reached. In that case, the mimimum is 0.

 

 

For the maximum [math]Q_{max}=1+B(K-2)[/math]:

 

[math]\sum_{i=1}^{K}|B-A{_i}| \stackrel{extend}{=}\sum_{i=1}^{K}(B+A{_i})-\sum_{i=1}^{K}(B+A_{i}-|B-A{_i}|)[/math] [math]=KB+1-\sum_{i=1,A{_i}>B}^{K}(B+A{_i}+B-A{_i})-\sum_{i=1,A{_i}\leq B}^{K}(B+A{_i}-B+A{_i})[/math] [math]=KB+1-\sum_{i=1,A{_i}>B}^{K}(2B)-\sum_{i=1,A{_i}\leq B}^{K}(2A{_i})[/math]. This will get maximal if you have [math]A{_i}=0 \forall A{_i}\leq B[/math], when it will be equal to [math]KB+1-2B \cdot 1_{A{_i}>B}[/math].

If one of the [math]A{_i}[/math] is equal to [math]1[/math] (and all other [math]A_{i}[/math] are [math]0[/math]), this will take its maximum value [math]KB+1-2B \cdot 1=1+B(K-2)[/math].

Edited by renerpho
  • Upvote 2

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this