Supongamos que tenemos un conjunto de enteros positivos de N, $s_1 ≤ s_2 ≤ s_3 ≤ \ldots ≤ sn$. Dados dos enteros positivos $a, b$, que número $x$ minimiza esta suma: $$\sum{s_i x} b(s_i -x)$$ I've only figured out that if $ a = b $, then the answer is the median of the set. However, I can't figure out what happens if $a \neq b$.
Respuestas
¿Demasiados anuncios?
gandalf61
Puntos
486
Vamos a llamar a la suma f(x).
Si $x<s_1$ todos los $s_i$ mayor que x, entonces f es la suma de n términos de cada uno de los cuales tiene pendiente-b. Así que la pendiente de f en la región es -nb.
A medida que x aumenta, se convierte en mayor que $s_1$. En la región de $(s_1, s_2)$ f es la suma de 1 plazo con pendiente a y (n-1) términos con pendiente-b. Así que f tiene pendiente a - (n-1)b = a + b - nb.
Y en general, si x se encuentra entre el$s_i$$s_{i+1}$, en este punto f tiene pendiente ka - (n-k)b = k(a+b) - nb. Eventualmente x es mayor que $s_n$, y la pendiente de f se convierte en na.
Para minimizar f usted sólo tiene que encontrar el valor de k en el que la pendiente de f cambia de negativa a positiva (recordemos que a y b son ambos valores positivos).
Considere la posibilidad de cualquier intervalo de $(s_k, s_{k+1})$ donde $s_k < s_{k+1}$. Para cualquier $x$ en este intervalo, hay $k$ elementos menos de $x$, e $n-k$ elementos mayor que $x$. Mientras permanezcamos en este intervalo, el aumento de $x$ por una pequeña cantidad $\Delta x$ aumenta la izquierda de la suma por $ak\Delta x$, pero disminuye la mano derecha de la suma por $b(n-k)\Delta x$.
Mantener ese principio en mente: Si existe un $k$ tal que
$$ ak = b(n-k) $$
a continuación, el mínimo de los valores de $x$ son alguno de aquellos dentro del intervalo de $[s_k, s_{k+1}]$ (que puede contener un único valor, si $s_k = s_{k+1}$).
De lo contrario, nos encontramos con el único positivo $k$ tal que
$$ a(k-1) < b(n-k+1) $$
pero
$$ ak > b(n-k) $$
Tal $k$ está garantizado que existen para los enteros positivos $a$ $b$ (por qué?), y, a continuación, se alcanza el mínimo en $x = s_k$.
Andreas
Puntos
36
$$\sum_{s_i < x} (x - s_i) + \sum_{s_i > x} b(s_i -x) = x (\sum_{s_i < x} 1 - b \sum_{s_i > x} 1) - \sum_{s_i < x} s_i + b \sum_{s_i > x} s_i $$ $$ = - b n x + x i ( a +b) - (a+b) \sum_{s_i < x} s_i + b \sum s_i $$ donde $i$ es el número donde $s_i < x < s_{i+1}$. Por lo $x$ debe minimizar
$$ F(i) = (i - \frac{b n}{a+b}) x -\sum_{k = 1}^i s_k $$
Tenemos la pendiente $G(i) = F(i) - F(i-1)$ con
$$ G(i) = (i - \frac{b n}{a+b}) x(i) - (i-1 - \frac{b n}{a+b}) x(i-1) ) - s_i $$
Deje $x(i)$ estar siempre en el centro de la suma de dos términos,$x(i)= 1/2(s_{i+1} + s_i)$$x(i-1)= 1/2(s_{i} + s_{i-1})$. Así
$$ 2 G(i) = (i - \frac{b n}{a+b}) (s_{i+1} + s_i) - (i-1 - \frac{b n}{a+b}) (s_{i} + s_{i-1}) ) - 2 s_i $$
Ahora podemos calcular el $i$ en el punto donde se $G(i)$ cambia de signo, de manera que aproximadamente el establecimiento $G(i) =0$ tenemos
$$ 0 = (i - \frac{b n}{a+b}) (s_{i+1} - s_{i-1}) - s_i + s_{i-1} $$
que es aproximadamente $$ i \simeq \frac{b n}{a+b} + \frac{ s_i - s_{i-1} }{s_{i+1} - s_{i-1}} \\ = \frac{b n}{a+b} + \frac{ 1}{1 + \frac{s_{i+1} - s_{i}}{s_i - s_{i-1} }} $$ y, de nuevo,$x(i)= 1/2(s_{i+1} + s_i)$. Tenga en cuenta que la última fracción es de la forma$\epsilon = 1/(1+x)$$x>0$, por lo que se puede lograr sólo a valores de entre $0$$1$. Por lo tanto, tenemos $$ i \simeq \frac{b n}{a+b} + \epsilon $$ con $\epsilon \in (0,1)$. Así obtenemos para $x$ $b/(a+b)$ésimo cuantil de la gama de $\{s_1 \cdots s_n\}$, si cuantiles son entendidas en un continuo sentido de$0$$1$. Ver el comentario por Rahul sobre el que dijo que ya, y la siguiente discusión.
Como un primer caso especial, para equidistante $s_i - s_{i-1} = d$, tenemos
$$ i \simeq \frac{b n}{a+b} + \frac{d}{2d} = \frac{b n}{a+b} + \frac12 $$ como era de esperar.
Como segundo caso especial, por $a=b$ hemos
$$ i \simeq \frac{n}{2} + \epsilon $$
así que esta es la mediana, como ya se ha encontrado en el OP.
