Upper bound of coefficient of variation computed with mean average deviation From $n$ data $x_i$ in $[0,1]$, I am computing a coefficient of variation $C=d/\mu$ where $d$ is the mean average deviation $d=1/n \sum_{i=1}^n |x_i-\mu|$ and $\mu$ is the standard mean $\mu=1/n \sum_{i=1}^n x_i$.

I am looking for an analytical expression of the upper bound of $c$.

I found that the case of largest deviation happens when $n-1$ data equals 0 and 1 equals 1. In this case, $\mu=1/n$, $d=2(n-1)/n^2$, so $C=2(n-1)/n$

However, I am not sure how to show that the maximum deviation happens when all but 1 data equal 0. Moreover, I think this result (if it is right) must have been shown properly before, but I cannot find by who and where.

Can you help me regarding the demo and the 2 latter points ?

Thanks !

EDIT

I think the following could be a demonstration, but I still have a doubt, as indicated below.

First, let us consider the data are sorted in ascending order and denote $l$ the number of points lesser or  equal than $\mu$, i.e. $l=|\{x_i \text{ s.t. } x_i\leq\mu\}|$. Then we define $\theta$ the sum of their values i.e. $\theta=\sum_{i=1}^l x_i$ and $\theta'=\sum_{i=l+1}^n x_i$, so:
\begin{align*}
C &amp; =\frac{d}{\mu}\\
 &amp; =\frac{\sum_{i=1}^{n}\left|x_{i}-\mu\right|}{\sum_{i=1}^{n}x_{i}}\\
 &amp; =\frac{\sum_{i=1}^{l}\left(\mu-x_{i}\right)+\sum_{i=l+1}^{n}\left(x_{i}-\mu\right)}{\theta+\theta'}\\
 &amp; =\frac{l\mu-\theta+\theta'-\left(n-l\right)\mu}{\theta+\theta'}\\
 &amp; =\frac{2l\mu-\theta+\theta'-\theta-\theta'}{\theta+\theta'}\text{ since }n\mu=\theta+\theta'\\
 &amp; =2\frac{l\mu-\theta}{\theta+\theta'}\\
 &amp; =2\left(\frac{l}{n}-\frac{\theta}{\theta+\theta'}\right)
\end{align*}

Moreover, increasing $\theta'$ and decreasing $\theta$ of the same value keeps $\mu$ constant and increases $d$, hence for $l$ and $\mu$ given, the  largest $C$ is reached with the smallest $\theta$ and the largest $\theta'$. In the best case, $\theta=0$ if the  $l$ values equal 0 and $\theta'=n-l$ if the $n-l$ values equal 1 and:
$$
C=\frac{2l}{n}
$$

The largest $C$ is not reached for $l=n$ since in this case $d=0$ and so does $C$. Therefore, the largest $C$ is reached for  $l=n-1$, so the upper bound of $C$ is $2(n-1)/n$, or approximately 2 when $n$ is large.

Note
I think that even though the result may be correct, I am not sure about the step from "$\theta$ should be min and $\theta'$ should be max" to "let us consider now series made of 0 and 1 only", since in this case, $\mu$ is not constant anymore, even though is is assumed in the previous step.

Anyone has a "clean" version for this ?
You're right in identifying the problem: we shouldn't assume that $\mu$ is constant. The solution seems to be a tiny tweak to your excellent work:

[1] Note that $0 \leq \theta / [\theta + \theta'] &lt;=1$

[2] Note that $2(l/n - \theta / [\theta + \theta'])$ is maximised when $\theta / [\theta + \theta']$ is minimised.

[3] In particular note that, despite the resulting change in $\mu$, the $l / n$ is constant because $l$ doesn't change as we reduce the first $l$ values towards $0$ or increase the $n-l$ values towards $1$. 

[3'] I just spotted for this to be true we need to define l to be the number of items  $\lt \mu$ not $\leq \mu$. Everything still seems to work.

[4] Whatever the value of $\theta'$ we can obtain the $0$ minimum by setting all the values below $\mu$ to $0$.

[5] So the maximum is $2l/n$ as you say.

[6] And this is maximised by choosing $l = n-1$ ($l=n$ is all the same which minimises)

[7] The final point to note is that with the first $n-1$ items as zero the expression is maximised when the $n$th value is $1$.



OK, let me try a slightly different way. There are two related challenges here:

1) What is the maximum value of d / $\mu$ where we have full flexibility over x values subject to $0 \leq x&lt;=1$?  NB In this case $\mu$ varies as the x values vary.  

2) What is the maximum value of d / $\mu$ where flexibility over the x values is additionally limited because their mean may not vary but must be equal to the fixed value $\mu$?

I think you're trying to solve 1) but you seem to suggest you're muddled because you're moving between fixing $\mu$ in your mind, but then noticing that the calculated value of the mean changes, because you're not in fact constraining the x values to have a fixed mean.

The "new" material was supposed to be [2] above. Let me try to be clearer. I pointed out that $0 \leq \theta / [\theta + \theta'] &lt;=1$. Now because you're not constraining the x values to result in a fixed mean the denominator i.e. $\theta + \theta'$ will vary as the x values vary. Nonethless the ratio will still be minimised when $\theta=0$ - as easy as that! From this it followed that you should set the $l$ x values to zero. Then that l = n-1 and that the top c value is 1. That's all in your proof already, so it's just a slightly different thought pattern which (I thought) avoids the muddle you thought you were in.

My other bit was my own concern, namely that in changing the x values you changed $\mu$ and hence potentially $l$. My solution was a tweak:
* Define $l$ so that it referred to values less than the mean
* Then simulataneously move all these $l$ xs to zero. The mean changes but exactly the same xs are less than the mean. what I was trying to prevent was a constructive approach where we reduced one x value to zero only to find one x value which was just below the old mean is now just above it. Perhaps this doesn't matter, but it felt clearer to me.

The second problem I mentioned above - where we constrain the changes in the x values so that the "new" mean after changing the x values is equal to the old mean $\mu$, a constant, is also interesting. In this case the maximum we can achieve is:

dmax = [ H * (1-$\mu$) + (n-H-1) * $\mu$ + 1 * ($\mu$-f) ] / n

where $0\leq f \lt 1$ and H is the largest integer such that:

$\mu$ = (H+f)/n

In this case we put:


H of the x values at 1
n-H-1 of the x values at 0
1 of the x values at f (note we could have f=0)


As a special case of this take $\mu$ = 1/n. Then:


f=0
H=1
dmax/$\mu$ = 2*(n-1)/n as before
You're right in identifying the problem: we shouldn't assume that $\mu$ is constant. The solution seems to be a tiny tweak to your excellent work:

[1] Note that $0 \leq \theta / [\theta + \theta'] &lt;=1$

[2] Note that $2(l/n - \theta / [\theta + \theta'])$ is maximised when $\theta / [\theta + \theta']$ is minimised.

[3] In particular note that, despite the resulting change in $\mu$, the $l / n$ is constant because $l$ doesn't change as we reduce the first $l$ values towards $0$ or increase the $n-l$ values towards $1$. 

[3'] I just spotted for this to be true we need to define l to be the number of items  $\lt \mu$ not $\leq \mu$. Everything still seems to work.

[4] Whatever the value of $\theta'$ we can obtain the $0$ minimum by setting all the values below $\mu$ to $0$.

[5] So the maximum is $2l/n$ as you say.

[6] And this is maximised by choosing $l = n-1$ ($l=n$ is all the same which minimises)

[7] The final point to note is that with the first $n-1$ items as zero the expression is maximised when the $n$th value is $1$.



OK, let me try a slightly different way. There are two related challenges here:

1) What is the maximum value of d / $\mu$ where we have full flexibility over x values subject to $0 \leq x&lt;=1$?  NB In this case $\mu$ varies as the x values vary.  

2) What is the maximum value of d / $\mu$ where flexibility over the x values is additionally limited because their mean may not vary but must be equal to the fixed value $\mu$?

I think you're trying to solve 1) but you seem to suggest you're muddled because you're moving between fixing $\mu$ in your mind, but then noticing that the calculated value of the mean changes, because you're not in fact constraining the x values to have a fixed mean.

The "new" material was supposed to be [2] above. Let me try to be clearer. I pointed out that $0 \leq \theta / [\theta + \theta'] &lt;=1$. Now because you're not constraining the x values to result in a fixed mean the denominator i.e. $\theta + \theta'$ will vary as the x values vary. Nonethless the ratio will still be minimised when $\theta=0$ - as easy as that! From this it followed that you should set the $l$ x values to zero. Then that l = n-1 and that the top c value is 1. That's all in your proof already, so it's just a slightly different thought pattern which (I thought) avoids the muddle you thought you were in.

My other bit was my own concern, namely that in changing the x values you changed $\mu$ and hence potentially $l$. My solution was a tweak:
* Define $l$ so that it referred to values less than the mean
* Then simulataneously move all these $l$ xs to zero. The mean changes but exactly the same xs are less than the mean. what I was trying to prevent was a constructive approach where we reduced one x value to zero only to find one x value which was just below the old mean is now just above it. Perhaps this doesn't matter, but it felt clearer to me.

The second problem I mentioned above - where we constrain the changes in the x values so that the "new" mean after changing the x values is equal to the old mean $\mu$, a constant, is also interesting. In this case the maximum we can achieve is:

dmax = [ H * (1-$\mu$) + (n-H-1) * $\mu$ + 1 * ($\mu$-f) ] / n

where $0\leq f \lt 1$ and H is the largest integer such that:

$\mu$ = (H+f)/n

In this case we put:


H of the x values at 1
n-H-1 of the x values at 0
1 of the x values at f (note we could have f=0)


As a special case of this take $\mu$ = 1/n. Then:


f=0
H=1
dmax/$\mu$ = 2*(n-1)/n as before