Sí.
Empecemos por simplificar la cuestión. El evento
T_1\sum_{i=1}^n T_i w_i \geq 0
es la unión de los eventos disjuntos (determinados por T_1=\pm 1 )
w_1 + \sum_{i=2}^n T_i w_i \geq 0,\ -w_1 + \sum_{i=2}^n T_i w_i \geq 0.
Tras una sencilla manipulación algebraica, y utilizando el hecho de que cada T_i tiene la misma distribución que -T_i (es "simétrico"), estos eventos son ambos equivalentes a los de la forma
\sum_{i=2}^n T_i w_i \leq w
para w=\pm w_1 . Aprovechando de nuevo las simetrías del T_i (para que todos los w_i no negativo) y reordenándolos, se puede escribir
\sum_{i=2}^n T_i |w_i| \leq w
donde |w_2| \ge |w_3| \ge \cdots \ge |w_n| .
Necesitamos calcular las probabilidades de que se produzcan dos eventos de este tipo y deseamos hacerlo de forma eficiente. Asumiré que la probabilidad debe calcularse con gran precisión, de modo que las aproximaciones serían inaceptables. (Para muchas configuraciones del |w_i| De lo contrario, las aproximaciones normales a las distribuciones podrían funcionar bien. Se puede realizar un análisis más profundo utilizando la función característica \phi de \sum_{i=2}^n T_i |w_i| que por definición es \phi(t) = \prod_{i=2}^n\left(\frac{\exp(-j |w_i|t)}{2} + \frac{\exp(j |w_i|t)}{2}\right)=\prod_{i=2}^n\cos(w_it); j = \sqrt{-1} .)
A partir de ahora, reduzca n por 1 , inicie la indexación con i=1 y asumir todos los w_i son positivos. (Obviamente, cualquier valor cero puede ser ignorado). 1 \le k \lt n . Considere la distribución de X = \sum_{i=1}^n T_i w_i condicionada a la primera k valores de T_i :
\Pr(X \le w\,|\, T_1, \ldots, T_k) = {\Pr}_{(T_{k+1},\ldots,T_n)}\left(\sum_{i=k+1}^n T_i w_i \le w - \sum_{i=1}^k T_i w_i = w_0\right).
Desde |T_i| \le 1 la suma de la izquierda está acotada:
-u_{k+1} = -(w_{k+1} + \cdots + w_n) \le \sum_{i=k+1}^n T_i w_i \le w_{k+1} + \cdots + w_n = u_{k+1}.
Dejemos que u_{k+1} sea el lado derecho: es una suma acumulativa de los w_i acumulado a partir de los valores más bajos de la derecha. Obviamente, ahora si u_{k+1} \le w_0 entonces X \le w es seguro; y si -u_{k+1} \gt w_0 entonces X \le w tiene una probabilidad nula. Esto lleva a una simple rama y límite algoritmo, porque no necesitamos buscar más para evaluar la distribución. Mientras que una enumeración exhaustiva habría tenido que examinar 2^{n-k} casos posibles, hemos hecho una determinación de su contribución a la distribución en O(1) tiempo.
No hay muchas esperanzas de que esta mejora conduzca a una el peor de los casos algoritmo que es mejor que O(2^n) en el rendimiento (aunque creo que se puede reducir a O(2^{n/2}) que -aunque mucho mejor- sigue sin ser polinómico). Sin embargo, la mejora es lo suficientemente buena como para que valga la pena considerarla, especialmente para valores moderados de n donde la enumeración exhaustiva empieza a ser impracticable (en algún punto por encima de 20 y ciertamente por encima de 40 ). Por lo tanto, pasemos a evaluar el algoritmo. ¿Cuál es su eficacia?
El peor caso es cuando la mayoría de los w_i tienen tamaños comparables, ya que entonces la heurística branch-and-bound rara vez logra algo. Afortunadamente, esta es exactamente la situación en la que el Teorema Central del Límite puede proporcionar excelentes aproximaciones. Por lo tanto, quizás sea aún más interesante explorar situaciones en las que los tamaños de las w_i están muy repartidos.
Para ello, he creado cuatro conjuntos de datos con n=15 de cuatro distribuciones con formas radicalmente diferentes: Beta (1/5,1/5) (fuertemente bimodal), Exponencial (modo alto cerca de cero), Uniforme y Gamma (20) (casi Normal, con valores muy cercanos a 20 ). Cada conjunto de datos se normalizó a un máximo de 1 . Utilizando el método de rama y límite, \Pr(X \le w) se calculó para 19 valores de w que van desde 0 hasta 2\sqrt{n} . (Los valores negativos de w no es necesario mostrarlo porque las distribuciones de X son casi simétricos). La figura muestra los resultados, graficando las probabilidades (la función de distribución acumulativa empírica de X ) en la fila superior y el eficiencia (en escalas log-lineales) en la fila inferior. La "eficiencia" es la relación entre el número de configuraciones necesarias para la enumeración exhaustiva ( 2^n ) al número de configuraciones consideradas por el algoritmo branch-and-bound.
![Figure]()
Para la distribución Beta, cuya fuerte bimodalidad limita esencialmente los cálculos a la mitad superior de los datos, las eficiencias son mayores. Como era de esperar, son menores para la distribución Gamma, cuyos valores son todos comparables. Sin embargo, incluso en este caso difícil, todas las eficiencias superan 3 .
Las eficiencias más pequeñas suelen ser para w=0 . Con el tiempo, la eficiencia aumentará a medida que |w| aumenta. En conjunto, estos resultados son una fuerte evidencia de que el enfoque descrito aquí no sólo es computacionalmente más eficiente que la enumeración exhaustiva, sino que tiende a ser mucho más eficiente.
La aplicación del algoritmo es directa y sencilla. R
El código es el siguiente. Incluye una sección que prueba el algoritmo (comparando su salida con una enumeración exhaustiva) y otra sección para reproducir la figura.
#
# The algorithm.
#
f <- function(w0, w) {
w <- sort(abs(w), decreasing=TRUE)
w.sum <- c(rev(cumsum(rev(w)))[-1], 0)
count <- 0 # Counts calls to f()
f <- function(u, u.sum, w0) {
count <<- count + 1
y <- sapply(w0 + c(-1,1)*u[1], function(w1) {
if (w1 < -u.sum[1]) return(0)
if (w1 >= u.sum[1]) return(1)
return(f(u[-1], u.sum[-1], w1))
})
return(mean(y)) # (This could easily be changed to accommodate
# other probabilities for the T[i].)
}
list(Value=f(w, w.sum, w0), Count=count)
}
#
# Test with complete enumeration. The plot pairs should exactly coincide.
#
binary <- function(a, b, zero=-1, one=1) rep(c(rep(zero, 2^a), rep(one, 2^a)), 2^b)
n <- 9
b <- sapply(1:n, function(a) binary(n-a, a-1))
par(mfrow=c(2,2))
set.seed(17)
for (i in 1:4) {
w <- rexp(n)
x <- b %*% w
y <- sapply(x, function(w0) f(w0, w)$Value) #$
plot(ecdf(x))
points(x, y, pch=16, cex=1/2, col="Red")
}
#
# Explore the efficiencies actually achieved.
#
n <- 15
qb <- function(q) qbeta(q, 1/5, 1/5); sigma <- sqrt(1/(1+2*1/5))/2
qg <- function(q) qgamma(q, 20)
dist <- list(Gamma=qg, Normal=qnorm, Uniform=qunif, Exponential=qexp, Beta=qb)
par(mfcol=c(2,4))
for (s in c("Beta", "Exponential", "Uniform", "Gamma")) {
d <- dist[[s]]
w <- d(((1:n)-1/2)/n)
w <- w / max(abs(w))
print(c(system.time({
y <- sapply(x <- seq(0, 2*sqrt(n), length.out=19),
function(w0) {x <- f(w0, w); c(x$Value, x$Count)})
})["elapsed"], count=sum(y[2, ])))
plot(x, y[1, ], ylim=c(1/2, 1), type="b", ylab="Probability", main=s)
plot(x, 2^n/y[2, ], ylim=c(1, 2^n), type="b", log="y", ylab="Efficiency")
}
0 votos
¿Se asumen algunas condiciones adicionales, como wi≥0 ∀i y ∑ni=1=1 ? ¿Qué pasa con la dependencia entre los Ti -- ¿se supone que son iid?
0 votos
No hay más condiciones. Sí, iid.
0 votos
No creo que este problema tenga una solución interesante si no se ponen al menos algunas condiciones a los posibles valores de los términos wi , i=1,…,n . Poner Y=T1(∑ni=1wiTi)=w1+T1(∑ni=2wiTi) (ya que T21≡1 ). Si w1 es (digamos) un número positivo grande s.t. w1>∑ni=2|wi| entonces P(Y≥0)=1 . Para obtener un resultado no trivial, creo que se necesita, como mínimo, algún tipo de límite en max .
2 votos
@Mico Su análisis reduce la pregunta a una ligera generalización: calcular \Pr(\sum_{i=2}^n T_iw_i\ge-w_1) . No se necesitan límites en el w_i para analizar ese problema. De mayor relevancia sería la información sobre los tamaños relativos de los w_i^2 y el tamaño de n porque eso permitiría obtener buenas soluciones aproximadas.
0 votos
@whuber - Muy rápido: ¿no debería haber un factor T_1 multiplicando \sum_{i=2}^n w_i T_i ? Para excluir las soluciones triviales (es decir, aquellas con probabilidad 0 y 1 ), se necesita algunos restricciones a w_i posiblemente con algún vínculo con n ¿verdad?
2 votos
@Mico Técnicamente, sí, pero un poco de reflexión le sugerirá cómo deshacerse de él: al multiplicar todo por T_1 ese factor desaparece de la suma y vuelve a aparecer multiplicado por w_1 . Por lo tanto, se puede dividir el problema en dos casos: uno en el que T_1=1 y el otro donde T_1=-1 (y -w_1 se sustituye por w_1 y el \ge se sustituye por \le ). Así que puedes resolver esos dos problemas (esencialmente idénticos) y combinar las soluciones. No se necesitan restricciones en ninguno de los w_i para desarrollar una solución general pero va a ser complicado.
0 votos
Supongo que se podrían "recorrer" todas las combinaciones posibles del T_2,...,T_n de los resultados. Eso debería ser fácil de hacer usando algún bucle pero computacionalmente ineficiente. Desgraciadamente no hay restricciones en el w_i .
0 votos
¿Busca un cálculo numérico dado un conjunto de w_i o algún tipo de aproximación algebraica?