Colas
Colas
Colas
Procesos de Poisson 49
Procesos de conteo 49
Primera definición 50
Análisis en tiempo del proceso de Poisson 53
Propiedades de los procesos de Poisson 55
Tercera definición de un proceso de Poisson 62
Teorema de Palm-Khintchine 68
Resumen del tema 69
Problemas 71
4
Estadística descriptiva
Histograma
El histograma consiste en una representación gráfica en forma
de barras, donde el eje horizontal (de abscisas) abarca el conjunto
de posibles valores de O (al menos, entre su mínimo y su máximo),
y la altura de cada barra indica bien la frecuencia relativa del con-
junto de datos que abarca su base, bien el número total de muestras
que quedan en dicha base.
5
6 una introducción amable a la teoría de colas
X = {3, 1, 6, 3, 4, 2, 4, 5, 2, 1, 1, 2, 2, 4, 6, 5, 4, 4, 3, 1}. 3
Ejemplo 1.2. Sea otra vez el caso del vector X del Ejemplo 1.1, de 15
valor
X = {3, 1, 6, 3, 4, 2, 4, 5, 2, 1, 1, 2, 2, 4, 6, 5, 4, 4, 3, 1}. 10
O1 = {5, 1, 5, 100}
O2 = {4, 5, 5, 6}
Media
Otro parámetro muy usado para describir el conjunto de datos es
la media (o media aritmética), que se obtiene de calcular
1
o,
n ∑ oi .
oi ∈O
G = {3, 3, 4, 2, 0, 2, 4, 3, 0, 4}
8 una introducción amable a la teoría de colas
3+3+4+2+2+4+3+4
G= = 2.5.
10
que se representa en la Figura 1.3. 2
Ejemplo 1.4. Sea el caso del Ejemplo 1.3. A partir del conjunto de
goles G se puede hacer el subconjunto de los resultados en los que
el equipo marcó al menos un gol, esto es
3+3+4+2+2+4+3+4
G g >0 = = 3.125.
8
Definición de probabilidad
Ejemplo 1.5. Sea el caso de un equipo de fútbol (FCB) con las esta-
dísticas indicadas en la Tabla al margen, para un histórico de 1000
partidos. En dicha tabla se indica el número de partidos ganados, Resultado Total vs. RMA Resto
empatados y perdidos por dicho equipo, distinguiéndose también Ganar 900 5 895
entre cuando se enfrenta a otro equipo (RMA) y contra el resto de Empatar 65 10 55
Perder 35 15 20
equipos. Total 1000 30 970
Considerando los resultados globales, el resultado “ganar” apa- Tabla 1.1: Resultados de un equipo
rece en 900 de los 1000 experimentos. En este contexto, cuando se FCB al jugar contra el resto de equipos
y contra el RMA.
dice que el equipo FCB tiene una probabilidad de 0,9 (o del 90 %)
de ganar un partido, se está suponiendo que cada partido es un
“experimento” independiente y que la probabilidad del evento
“ganar” se corresponde con la frecuencia relativa medida de dicho
evento. De esta forma, se parte de la estadística descriptiva de los
resultados del equipo de fútbol para construir un modelo que per-
mita predecir (o explicar) su comportamiento, según la teoría de la
probabilidad
0 ≤ Pr(si ) ≤ 1
∑ Pr(si ) = 1
S = {1, 2, 3, 4, 5, 6}
Probabilidad condicionada
B
Ejemplo 1.7. Sea el caso de dos dados, A y B, que se tiran a la vez A
1 2 3 4 5 6
1750 veces, con los resultados de la Tabla 1.2. La probabilidad de 1 45 45 43 41 49 58
sacar un 4 con el dado A cuando sale un 3 en el dado B se expresa- 2 58 55 42 49 49 44
3 53 47 40 44 44 45
ría como: 4 47 60 40 48 58 46
5 51 59 57 50 41 54
Pr( A = 4, B = 3) 6 45 56 42 60 48 53
Pr( A = 4 | B = 3) = , Tabla 1.2: Resultado de lanzar 1750
Pr( B = 3)
veces los dados A y B.
que precisa: (i) por una parte, calcular la frecuencia relativa del
evento
Pr( A = 4, B = 3) ,
que sucede en 40 de los 1750 casos (según se aprecia en la tabla), y
(ii) por otra parte, calcular la frecuencia relativa del evento
Pr( B = 3) ,
12 una introducción amable a la teoría de colas
40/1750 40 10
Pr( A = 4 | B = 3) = = = ≈ 0,151,
264/1750 264 66
que es similar a la probabilidad de que el dado A saque un 4:
47 + 60 + 40 + 48 + 58 + 46 299
Pr( A = 4) = = ≈ 0,166 ,
1750 1750
lo que, como se verá más adelante, no es casualidad.
Ejemplo 1.8. Sea otra vez el caso del Ejemplo , con los 1000 parti-
dos del equipo FCB resumidos al margen, donde se supone que las Resultado Total vs. RMA Resto
frecuencias relativas sirven para modelar el sistema con probabili- Ganar 900 5 895
dades. Empatar 65 10 55
Perder 35 15 20
La probabilidad de que el equipo FCB gane se estimó como
Total 1000 30 970
900 9
Pr( G ) = = ,
1000 10
bastante próxima a la unidad. También se puede calcular la proba-
bilidad de que FCB juegue contra RMA, que se obtiene como
30 3
Pr( RMA) = = .
1000 100
La probabilidad de que un partido sea una victoria contra RMA
se obtiene como
5 1
Pr( G, RMA) = = ,
1000 200
mientras que la probabilidad de ganar condicionada a jugar contra
el RMA (o, lo que es lo mismo, la probabilidad de que un partido
contra RMA sea una victoria) se calcula como
Distribución marginal 5
Pr( G | RMA) = = 1/6.
30
Como se ha visto en los ejemplos anteriores, a veces se dispone
de información desglosada sobre dos tipos de eventos diferentes,
pero se precisa únicamente caracterizar el comportamiento de uno
de ellos. En una situación con dos variables aleatorias, X e Y, la
distribución marginal de X se define como la distribución de dicha
variable sin hacer referencia a la otra variable Y, y se obtiene direc-
tamente para cualquier valor x como
Pr( X = x ) = ∑ Pr(X = x, Y = y)
y
repaso de estadística y probabilidad 13
Ejemplo 1.9. Siguiendo con el caso de los dados del Ejemplo 1.7, el
número de veces que con el dado A se sacó un 1, 2, . . . es, respec-
tivamente, 281, 297, 273, 299, 300 y 300. Dividiendo estos valores
por el número total de lanzamientos (1750), se puede estimar la
B
distribución marginal de los resultados del dado A: A
1 2 3 4 5 6
1 45 45 43 41 49 58 281
Pr( A) ≈ {0.161, 0.169, 0.156, 0.171, 0.171, 0.171} , 2 58 55 42 49 49 44 297
3 53 47 40 44 44 45 273
todos ellos valores muy próximos a 1/6, como era de esperar. 4 47 60 40 48 58 46 299
5 51 59 57 50 41 54 300
6 45 56 42 60 48 53 300
Independencia 299 322 264 293 298 300 1750
Repetición de la Tabla 1.2, con valores
totales: lanzamientos de A y B.
Como se ha indicado, la probabilidad condicionada permite
identificar si los diferentes tipos de eventos en un conjunto de ob-
servaciones están relacionados entre sí: en el caso del Ejemplo 1.8
se ha comprobado que la probabilidad de ganar un partido depen-
de del contrincante, mientras que en el Ejemplo 1.9 se aprecia que
los resultados de un dado no dependen de los de otro dado. Este
tipo de análisis permiten definir la independencia entre diferentes
eventos, como se hace a continuación.
Dos sucesos son independientes si el hecho de que uno suceda no
afecta a que se pueda producir el otro: si A y B son independientes,
la probabilidad de que A se produzca no varía en función de que
B se haya producido o no (esto es, de que se considere B como
condición). Por lo tanto, la probabilidad condicionada permite
comprobar si A y B son independientes, dado que en tal caso se
tiene que cumplir que
Pr( A | B) = Pr( A) ,
Pr( A ∩ B) = Pr( A, B) = 0
Propiedades de la probabilidad
1 1 2
Pr(5 ∪ par) = Pr(5) + Pr(par) = + = .
6 2 3
La probabilidad de que salga un número par o un valor mayor
que tres sería
1 1 2 2
Pr(> 3 ∪ par) = Pr(> 3) + Pr(par) − Pr(> 3 ∩ par) = + − = .
2 2 6 3
∑ Pr( Bi ) = 1
i
Ejemplo 1.12. En el caso del fútbol, el subconjunto “vs. RMA” y Resultado Total vs. RMA Resto
“Resto” constituyen una partición del espacio de eventos “Total”. A Ganar 900 5 895
partir de esto, la probabilidad de ganar se puede expresar como Empatar 65 10 55
Perder 35 15 20
Total 1000 30 970
que queda
5 30 895 970 900
Pr( G ) = + = ,
30 1000 970 1000 1000
como era de esperar.
Momentos y esperanzas
µ = E[ X ] = ∑ xi Pr(xi ),
y pretende representar la “tendencia” del conjunto de valores de la
distribución.
µ2 = E[ X 2 ] = ∑ xi2 Pr(xi ),
y se trata de una suma de términos estrictamente positivos, propor-
cionando una idea de la “amplitud” de los valores de la variable
aleatoria.10 10
Puede interpretarse como la energía
de una determinada variable.
La varianza se define como el momento de segundo orden res-
pecto a la media,
Propiedades
Si X es una variable aleatoria y k una constante, a partir de las
definiciones anteriores se pueden deducir las siguientes propieda-
des:
E[kX ] = kE[ X ]
E[(kX )2 ] = k2 E[ X 2 ]
E[ X 2 ] = E[ X ]2 + σ 2 ( X ) (1.3)
2 2
σ (k + X ) = σ ( X )
σ 2 ( X + Y ) = σ 2 ( X ) + σ 2 (Y )
18 una introducción amable a la teoría de colas
Esperanza condicionada
De forma análoga al caso de la media condicionada, visto en es-
tadística descriptiva, se puede definir la esperanza de una variable
aleatoria condicionada a que se cumpla un cierto requisito. De esta
forma, la esperanza de una variable aleatoria X condicionada a que
otra variable aleatoria Y valga y se puede expresar como
x · Pr( X = x, Y = y)
E[ X | Y = y ] = ∑ x Pr(X = x | Y = y) = ∑ Pr(Y = y)
Ejemplo 1.15. Sea una variable aleatoria X que puede tomar los
valores {1, 2, 3, 4} con probabilidades {1/5, 1/5, 1/5, 2/5}, respecti-
vamente. La esperanza de dicha variable aleatoria es
1 1 1 2 14
E[ X ] = 1 · +2· +3· +4· = .
5 5 5 5 5
1 · Pr( X = 1) + 2 · Pr( X = 2) 3
E[ X | X ≤ 2] = = .
Pr( X = 1) + Pr( X = 2) 2
1
Pr(éxito intento 1) = Pr(1 Mbps) Pr(éxito a 1 Mbps) =
4
La esperanza pedida se puede expresar como
E[ N | fallo intento 1] = 1 + E[ N ] ,
E[ N ] = 4 .
E[ T | B] = 20 h + E[ T ] , E[ T |C ] = 5 h + E[ T ].
Distribución uniforme
Una variable aleatoria discreta uniforme (Figura 1.9) es aquella
que puede tomar n posibles valores, cada uno de ellos con probabi-
lidad 1/n. Por lo tanto, su función de masa de probabilidad viene
0
dada por 2 3 4 5 6
1 Figura 1.9: Variable aleatoria uniforme-
Pr( xi ) = ∀ i. mente distribuida entre 2 y 6.
n
20 una introducción amable a la teoría de colas
a+b n2 − 1
µ= σ2 = .
2 12
Ensayo de Bernoulli
Un ensayo de Bernoulli (ilustrado en la Figura 1.10) se define co-
mo un experimento que se realiza una única vez y puede salir bien
o mal. Se trata de la variable aleatoria discreta más sencilla, que
únicamente puede tomar dos valores, típicamente 0 y 1, donde el 1 0
0 1
representa un éxito y sucede con probabilidad p, y el 0 representa Figura 1.10: Ensayo de Bernouilli con
un fracaso y sucede con probabilidad 1 − p. Su media y varianza p = 3/4.
µ=p σ 2 = p (1 − p ).
0,3
Distribución geométrica
En este caso, se repite el ensayo de Bernouilli hasta que se pro-
duzca un éxito. Ahora la variable aleatoria es el número de expe- 0,2
rimentos necesarios hasta que se produjo dicho éxito (Figura 1.11).
Suponiendo que los ensayos se realizan de forma independiente, la
probabilidad de necesitar k experimentos en total viene dada por 0,1
Pr(k) = (1 − p)k−1 p, k = 0, 1, 2, . . .
0
esto es, que se produzcan k − 1 fallos consecutivos, cada uno con 0 2 4 6 8 10
k
probabilidad (1 − p), y un éxito al final, con probabilidad p. La
Figura 1.11: Variable aleatoria geomé-
distribución geométrica tiene como media y varianza trica con p = 1/5.
1 1− p
µ= σ2 = .
p p2
Distribución binomial
La distribución binomial modela el caso de n ensayos de Ber-
nouilli independientes, cada uno con una probabilidad de éxito p,
siendo la variable aleatoria de interés el número total de éxitos. Las
probabilidades de n éxitos y n fracasos resultan inmediatas de cal-
cular (pn y (1 − p)n , respectivamente), mientras que para el resto
de probabilidades es preciso tener en cuenta que hay varias formas
repaso de estadística y probabilidad 21
en las que pueden ocurrir los éxitos, por lo que es preciso emplear
combinatoria. La probabilidad de tener k éxitos viene dada por
p = 0,2
0,2
n k n!
Pr(k) = p (1 − p ) n − k = p k (1 − p ) n − k , (1.4) p = 0,5
k k!(n − k)!
y la media y varianza de la distribución binomial resultan ser 0,1
µ = np σ2 = np(1 − p).
0,1
De hecho, considerando cada uno de los n experimentos como
un ensayo de Bernouilli, de media p y varianza p(1 − p), la media
0,0
y la varianza de la distribución binomial se pueden deducir a partir
de las propiedades de la suma de variables aleatorias: la media 0 10 20 30 40
es n veces la media de un ensayo (p) y la varianza es n veces la Figura 1.12: Variables binomiales con
n = 40 y dos valores de p.
varianza de un ensayo (p(1 − p)). Se representan en la Figura 1.12
dos variables aleatorias binomiales.
Distribución de Poisson
La distribución de Poisson se puede interpretar como una dis-
tribución binomial, donde el número de ensayos a realizar es muy
grande, y la probabilidad de éxito muy baja. Sirve por tanto para
modelar sucesos poco frecuentes,13 con una media que viene dada 13
En la binomial resulta complicado
por calcular probabilidades para valores
elevados de n, dada la presencia del
λ , n · p. factorial.
lı́m FX ( x ) = 0, lı́m FX ( x ) = 1,
x →−∞ x →+∞
Función de densidad
La función de densidad sirve para representar la forma en que
una variable aleatoria continua se distribuye. Dada la variable alea-
toria X, se define como aquella funcion no-negativa f X que cumple
que
Z b
Pr( a < X ≤ b) = f X ( x )dx,
a
por lo que también se puede interpretar como la derivada de la
función de distribución FX (si existe), esto es
d
f X (x) = FX ( x ).
dx
Por lo tanto, se tiene que la función de distribución se puede
expresar como la integral de la función de densidad,
Z x
FX ( x ) = f X (y)dy.
−∞
por lo que se puede decir (aunque no sea muy formal) que aquellos
valores de x donde f X sea mayor son más probables, (teniendo en
cuenta que la probabilidad de un determinado valor es cero).
a+b ( b − a )2
µ= σ2 = ,
2 12
La media de los valores mayores que la media se puede expresar
mediante una esperanza condicionada
Rb
( a+b)/2 x f ( x )dx
E[ X | X > ( a + b)/2] = R b
( a+b)/2 f ( x )dx
repaso de estadística y probabilidad 25
E[ X 2 ] = E[ X ]2 + σX2 ,
E [ X + Y ] = E [ X ] + E [Y ] ,
0,5
donde Pr( X1 < τ ) es, por definición, FX1 , y se trata de una función
a trozos (Figura 1.17 al margen)
1 f
F
0, si x ≤ 0
FX1 ( x ) = x, si 0 ≤ x ≤ 1
1, si x ≥ 1
0,5
Xmáx = máx{ X1 , X2 , . . . , X N },
Problemas
Solución. K = 3/4, E[ X ] = 0.
Solución. 150 µs
Problema 1.6. (Ej. 14/15) Una tarjeta inalámbrica tiene dos tasas
de transmisión, 24 y 48 Mbps y su algoritmo de selección de tasa es
completamente aleatorio, eligiendo a cada trama una de las tasas al
azar. Las condiciones del canal son muy malas, de tal forma que las
tramas a 24 Mbps son recibidas con éxito el 10 % de las ocasiones
y el resto, nunca. Si las tramas son de 480 bytes, calcule (en µs) el
tiempo medio que se tarda en enviar una trama con éxito.
Solución. T= 2400 µs
f ( x ) = a + bx2 , 0 ≤ x ≤ 1,
Solución. 1/6
f X ( x ) = λe−λx , x≥0
1
Esperanza y desviación típica
33
34 una introducción amable a la teoría de colas
1 −t/5
T ∼ exp(5), f T (t) = e , t≥0.
5
σX2 = E[ X 2 ] − E[ X ]2 .
x M : F ( x M ) = 0.5,
ln 2 1
xM = ≈ 0.7 .
λ λ
Por lo tanto, para el caso de una variable aleatoria exponencial se
tiene que la mediana es un 70 % del valor de la media, por lo que la
distribución se encuentra “escorada” hacia los valores próximos a
cero.
La función de supervivencia
La función de supervivencia es otro nombre de la función com-
plementaria FC
F C ( x ) , 1 − F ( x ).
S(t) = e−λt .
Por otra parte, a partir de dos horas (120’) sabe que, con total
seguridad, en media hora o menos terminará (Pr( Tr (t) > 300 ) =
0), dado que ninguna película dura más de 150’.
Pr( Tr > 1)
Esperanza condicionada
Sea una variable aleatoria X con función de densidad
f (t) = λe−λt .
E[ X | X > k ] ,
E[ X | X > k ] = k + E[ X ] ,
Z ∞
Pr( X1 < X2 ) = Pr( X2 > X1 | X1 = τ ) f X1 (τ )dτ (2.3)
0
Z ∞
= Pr( X2 > τ ) f X1 (τ )dτ ,
0
k −1
1 −λx
F ( x, k, λ) = 1 − ∑ n!
e (λx )n .
n =0
λi
∑j λj
la variable aleatoria exponencial 45
Problemas
1 −λa )
Solución. λa (1 − e
Solución. 70 e.
Solución. 52.834 e.
(1 − PT · PM ) ( X + Y ) = 1 − (1 − e− Nλ )(1 − e− Mλ ) ( X + Y )
Solución.
Solución. 1− λ2 − λ1 C
λ1 + λ2 e
Solución. e−36,5 .
Solución. 60 ms.
Procesos de Poisson
Procesos de conteo
49
50 una introducción amable a la teoría de colas
N04,1 = 4
Figura 3.1: Ejemplo de un proceso con
cuatro llegadas.
Primera definición
33 − 3
Pr( N0T = 3) = e ≈ 0,22
3!
Estacionariedad e independencia
A raíz de la definición de proceso de Poisson se puede hablar
de dos propiedades que pueden tener los procesos de llegadas
(no sólo este tipo de procesos): estacionariedad e independencia.
Por un lado, la primera hace referencia a que la probabilidad de
n llegadas en un intervalo de tiempo t viene siempre dada por la
misma variable aleatoria discreta de Poisson (de media λt), sin
importar del instante inicial de dicho intervalo. Se puede definir
como de la siguiente manera:
52 una introducción amable a la teoría de colas
Pr( N (t) = 0)
(λt)0 −λt
Pr( X1 > t) = Pr( N (t) = 0) = e = e−λt ,
0!
que es, por definición, la función de supervivencia de una variable
aleatoria exponencial de media 1/λ. Por lo tanto, se deduce que el
tiempo hasta el primer evento X1 se distribuye según una variable
aleatoria exponencial.
Sea ahora el caso de la segunda llegada, que ocurre tras un tiem-
po X2 . Para analizar cómo se distribuye dicho tiempo, se supone
que el tiempo X1 de la primera llegada ocurre en un determinado
instante s, y se analiza la probabilidad de que X2 sea mayor que t
condicionada a este valor de X1 , según se ilustra en la Figura 3.6:
(λt)0 −λt
Pr( X2 > t | X1 = s) = Pr(0 eventos en (0, t)) = e = e−λt .
0!
A la vista de lo anterior, se tiene que el tiempo entre la primera 3
El desarrollo presentado sirve para
deducir la segunda definición par-
y la segunda llegada X2 también se distribuye según una variable tiendo de la primera. Para demostrar
aleatoria exponencial, con el mismo parámetro λ. Este mismo desa- la equivalencia de ambas definicio-
rrollo se puede repetir para la llegada i-ésima, obteniéndose que nes (que lo son) debería realizarse el
razonamiento en el otro sentido, es
la variable Xi se distribuye según una variable aleatoria exponen- decir, partir de la segunda definición y
cial de media 1/λ. De esto se deduce la siguiente definición de un demostrar la primera.
proceso de Poisson:3
54 una introducción amable a la teoría de colas
Ejemplo 3.6. Supóngase que los goles siguen una variable aleatoria
discreta de Poisson y que un equipo ha metido un gol en la primera
parte. Se plantea ahora la cuestión de estimar cuándo se produjo
dicho gol, esto es, ¿en qué ventanas de tiempo es más probable que
se haya producido dicho gol? ¿Hay zonas calientes donde el equipo
marque con más probabilidad?
Una posible intuición sería suponer que el gol debe haberse pro-
ducido hacia la mitad del tiempo considerado (como se ilustra en
la parte superior de la Figura 3.7). Otra opción sería pensar que,
Figura 3.7: Sabiendo que un equipo ha
dado que el tiempo entre goles es exponencial, el gol debe tener
marcado un único gol en la primera
una función de densidad que se pareciese a la exponencial (par- parte, se podría plantear si es más
te inferior de la Figura 3.7). Como se verá a continuación, ambas probable que hubiese ocurrido hacia
la mitad del primer tiempo (arriba) o
interpretaciones son incorrectas. hacia el principio (abajo).
para cualquier valor de s ∈ [0, t]. Esto se puede expresar, por defini-
ción de probabilidad condicionada, como
Pr( X1 < s, N (t) = 1) = Pr(1 llegada en (0, s)) × Pr(0 llegadas en (s, t))
(λs)1 −λs (λ(t − s))0 −λ(t−s)
= e × e
1! 0!
mientras que el denominador de la parte derecha (3.2) queda como
PASTA
El acrónimo PASTA proviene del inglés Poisson Arrivals See Time
Averages, y podría traducirse como “un proceso de llegadas de Pois-
son ve medias temporales,” siendo una de de las propiedades de
mayor importancia en la teoría de colas.4 Para definirla, es preciso 4
También se le conoce como la propie-
distinguir entre dos “medias” en un proceso aleatorio: dad ROP, de Random Observer Property
56 una introducción amable a la teoría de colas
6,4 ms
ρ= = 0,64
10 ms
por lo que se puede decir que el canal está ocupado el 64 % del
tiempo. Sin embargo, un proceso de muestreo periódico cada 10 ms
no medirá esta ocupación, ya que siempre “verá” lo mismo el 100 %
del tiempo: bien el canal libre, bien el canal ocupado (según se
ilustra en la figura a continuación).
por lo que
b c
Pr(b) = y Pr(c) = ,
t t
es decir: la probabilidad de que la llegada se produzca en un deter-
minado intervalo es igual a la longitud relativa de dicho intervalo
con respecto al total.5 Con esto, (3.3) queda como 5
Este hecho también se podría haber
deducido del análisis de la distribu-
a b c ción condicionada de una llegada,
E [Y ] = A · +B· +C· , visto en el apartado anterior.
t t t
3 horas 21 horas
N= × 40 alumnos + × 0 = 5 alumnos.
24 horas 24 horas
N1 = {3, 8, 9}
N2 = {1, 4, 7, 10}
NT = {1, 3, 4, 7, 8, 9, 10}
XT = mı́n( X1 , X2 ),
procesos de poisson 59
1 −t/6
f X (t) = e , t≥0
6
Supóngase que este proceso se divide en dos, según el tiempo
entre una llegada y la siguiente Xi :
N (t) → N
N1 (t) → N1
N2 (t) → N2
e−λt (λt)n+m
Pr( N = n + m) = . (3.5)
(n + m)!
= Pr( N2 = m | N = n + m).
λ T = 24 × 10 = 240 paquetes/ms.
N ( Ti ) ∼ Poisson(λTi ).
Funciones o (h)
Se dice que una función f ( x ) es o (h) si se cumple que
f (h)
lı́m =0
h →0 h
procesos de poisson 63
h2
lı́m = lı́m h = 0
h →0 h h →0
La intuición detrás de este artificio de funciones o (h) es que per- Figura 3.18: La función f ( x ) = x2 es
miten realizar aproximaciones al manejar infinitesimales, ya que o ( h ).
dichas funciones podrán “despreciarse” frente a componentes que
crezcan (o se empequeñezcan) según una función lineal.
Resulta sencillo demostrar las siguientes propiedades
Tercera definición
En un proceso de llegadas a tasa λ, durante un intervalo de
tiempo t deben producirse en media λt llegadas. Esta definición
se basa en las funciones o (h) para caracterizar lo que pasa cuando
dicho intervalo t tiende a ser de tamaño mínimo.
(i) N (0) = 0
(ii) N (t) tiene incrementos independientes y estacionarios.
(iii) Pr( N (h) = 1) = λh + o (h)
(iv) Pr( N (h) ≥ 2) = o (h)
cuyo desarrollo es
cuyo desarrollo es
Caso de P0 (t)
P0 (t + h) = P0 (t) · (1 − λh + o (h)),
P0 (t + h) − P0 (t) o (h)
= −λP0 (t) + P0 (t). (3.9)
h h
o (h)
Calculando el límite cuando h → 0, el término h desaparece
(dado que P0 (t) es una constante), por lo queda
P0 (t + h) − P0 (t)
lı́m = −λP0 (t). (3.10)
h →0 h
P0 (t) = Ke−λt ,
procesos de poisson 67
P0 (t) = e−λt .
Caso de P1 (t)
P1 (t) = λte−λt .
Caso de Pn (t)
Teorema de Palm-Khintchine
Problemas
Solución. 1/2 s.
Solución. 1 − e−0,32
1
Solución. λ eλT − 1
Problema 3.8. (Ej. 11/12) A un servidor con una única CPU y una
cola de espera infinita llegan peticiones según un proceso de Pois-
son de tasa λ peticiones/segundo. Una vez que la CPU comienza
a atender una petición, el tiempo que tarda en completarla se pue-
de modelar con una variable aleatoria exponencial de media µ−1
segundos. Se pretende analizar el servicio recibido por la segunda
petición que llega al sistema. En concreto, se desea conocer para la
segunda petición:
1. Probabilidad de que tenga que esperar.
73
74 una introducción amable a la teoría de colas
Definición
s3
s2
s1
0 1 2 3 n-2 n-1 n
Xk = { s3 , s1 , s1 , s2 , . . . , s1 , s3 , s1 }
donde la secuencia si0 , si1 , si2 , . . . , sin representa los estados por los
que ha pasado el proceso desde el instante 0 hasta el instante n.
Pr( X7 = S | X6 = C, X5 = S, X4 = C, X3 = C, X2 = C, X1 = C ),
Pr( X7 = C | X6 = C, X5 = S, X4 = C, X3 = C, X2 = C, X1 = C ),
En este caso, según las reglas para repartirse los penalties, para
calcular estas probabilidades no hace falta saber toda la historia del
proceso, dado que el lanzador del siguiente penalty sólo depende
del lanzador actual, esto es:
Pr( X7 = C | X6 = C, X5 = S, X4 = C, X3 = C, X2 = C, X1 = C )
= Pr( X7 = C | X6 = C )
Origen • /• /•
Ejemplo 4.3. Una red multi-salto que emplee un algoritmo de
forwarding aleatorio se podría modelar con una cadena de Markov,
/ • / •
dado que la probabilidad de que un mensaje llegue a un nodo sólo • Destino
depende del nodo en que se encuentre, y no de todos los nodos que
haya visitado.
pij ≥ 0, ∀i, j
k
∑ pij = 1, ∀i
j =1
0.5
78 una introducción amable a la teoría de colas
0.6
)
0.8
) x
0.4 8 0 ic 1 2 0.9
0.20 0.10
con la correspondiente matriz P2 al margen (más sencilla).
0.4 0.6 0
P2 = 0.2 0 0.8
Como ilustra el ejemplo anterior, en general será sencillo 0.1 0 0.9
añadir estados “innecesarios” que aumenten la complejidad de la
cadena. Sin embargo, también puede ocurrir que existan varias for-
mas de modelar un sistema, en función de lo que se desee analizar,
y que no resulte sencillo determinar cuál es la más adecuada. Es
por ello que a la hora de modelar un sistema resulta crítico dedi-
car tiempo a determinar el número y significado de cada estado,
teniendo en cuenta que siempre se ha de cumplir la propiedad de
Markov: un estado debe definir una situación con toda la informa-
ción necesaria para que la historia pasada del proceso no afecte a lo
que pueda suceder en el futuro.
Ejemplo 4.8. Sea un modelo simple para predecir el tiempo, que a Mañana
partir de si hace calor o frío hoy estima con qué probabilidad hará Hoy Pr(Calor) Pr(Frío)
Calor 0.40
calor o frío mañana, según la Tabla 4.4. Frío
0.60
0.30 0.70
Dado que sólo es preciso saber el tiempo hoy para predecir el de Tabla 4.4: Modelo para el tiempo con
mañana, este sistema se puede modelar con una cadena de Markov una memoria de un día.
0.4 0.7
) )
0.6 8 CT i F FF
0.3
1
1
E [ Di ] = .
1 − pii
Irreducibilidad
En los ejemplos vistos hasta ahora, se puede comprobar que,
partiendo desde cualquier estado, es posible “alcanzar” cualquier
otro estado.3 Sin embargo, esto no es necesariamente cierto en 3
Esto es, siempre hay un “camino”
todas las cadenas de Markov, como se ilustra en el siguiente caso: para llegar desde cualquier estado a
cualquier otro estado.
1
)
1 2 f 1
si → s j
si → s j
s j → sk
si → s k
)
1
Sin embargo, la propiedad de accesibilidad no es conmutativa, 1 2 f 1
dado que las flechas son unidireccionales: por ejemplo, en la cadena
representada al margen se cumple que 1 → 2 pero no que 2 → 1.
Si si → s j y si ← s j , se dice que los estados si y s j se comunican
(entre sí), y se representa como
si ↔ s j
0,2
Se puede comprobar que dicha cadena tiene tres clases: {1, 2},
{3} y {4} (por la definición de accesibilidad, un estado siempre se
comunica consigo mismo).
0,3 0,8
Recurrencia
Partiendo de un estado en una cadena de Markov, puede ocu-
rrir que: (i) nunca se abandone, (ii) se vuelva a visitar pasado un
tiempo, o (iii) se abandone para no volver nunca. Según el caso, se
pueden definir diferentes tipos de estado.
A y B).
Ejemplo 4.13. Sea otra vez el caso de la cadena del Ejemplo 4.12,
con el siguiente diagrama de estados y matriz P al margen.
0,5 0,5 0 0
0,2 0,5 0,5 0 0
0,5 P=
0,2
0,2 0,2 0,4
0,5
) x 0 0 0 1
0,5 8 1T i 2 ir 3 5 4 1
0,5 0,2 0,4
0,2
cadenas de markov de tiempo discreto 83
En una cadena irreducible (esto es, que sólo tiene una clase), o
todos los estados son recurrentes, o todos son transitorios.
Ejemplo 4.14. Sea una cadena con dos estados {s1 , s2 } como la
ilustrada en el diagrama al margen, que parte en el instante 0 del Cadena para el ejemplo 4.14:
estado s1 , esto es X0 X1 X2
Pr( X0 = s1 ) = 1
De aplicar la expresión (4.2) para el caso de X1 resulta s1
p11
p12
/s1 p11
p12
/s> 1
X0 X1 X2
Pr( X2 = s1 ) = Pr( X2 = s1 | X1 = s1 ) Pr( X1 = s1 )+
Pr( X2 = s1 | X1 = s2 ) Pr( X1 = s2 ) s1
p11
/s1 p11
/s> 1
p12 p12
Ejemplo 4.15. Sea otra vez el modelo del tiempo con las proba- Mañana
bilidades de transición en la tabla al margen. Según este modelo, Hoy Pr(Calor) Pr(Frío)
sabiendo lo que sucede hoy, se puede calcular la probabilidad de Calor 0.60 0.40
Frío 0.30 0.70
lo que pueda suceder mañana. Por lo tanto, si hoy hace calor (c),
mañana también hará calor con una probabilidad de pcc =0.6, y frío
(f) con una probabilidad de pc f =0.4. 0.4
"
Una vez que se ha estimado lo que puede pasar mañana, se 0.6 8 C b F f 0.7
puede calcular la probabilidad de que haga calor pasado mañana
0.3
Por lo tanto, si hoy hace calor, pasado mañana hará calor con una
probabilidad de
(n)
πi , Pr( Xn = si ),
K
(n)
∑ πi = 1.
i =1
Ejemplo 4.16. Siguiendo con el ejemplo del tiempo, sea hoy el día
n = 0 y hace calor. Esto se representa como
Ecuaciones de Chapman-Kolmogorov
Como se ha visto en el ejemplo anterior, por la ley de la probabi-
lidad total en una cadena de Markov se cumple que
π ( n −1) = π ( n −2) P
esto es,
π ( n ) = π ( n −2) P 2 .
π ( n ) = π (0) P n (4.3)
Ejemplo 4.18. Sea el ejemplo del tiempo, con las siguientes poten-
cias de la matriz P:
! ! ! Probabilidad de
0.6 0.4 0.48 0.52 0.444 0.556 n Calor Frío
2 3
P= , P = , P = 0 1.00 0
0.3 0.7 0.39 0.61 0.417 0.583 1 0.60 0.40
2 0.48 0.52
Se puede comprobar que si π (0) = (1, 0), entonces las probabili- 3 0.444 0.556
4 0.4332 0.5668
dades de calor y frío en el día n (recopiladas en la tabla al margen) Tabla 4.6: Probabilidades de calor y
coinciden con π (0) Pn . frío según la Tabla 4.5.
compone de:
0 1
P2,n ∗ = (0, 1)
Por lo tanto:
!
n (1/4)n 1 − (1/4)n
P = .
0 1
90 una introducción amable a la teoría de colas
Periodicidad
Los componentes de Pn determinan la probabilidad de encon-
trarse en el estado s j partiendo del estado si y, por lo tanto, también
determinan la probabilidad de no encontrarse en cualquier estado
en un momento dado. Sea el caso de la cadena de Markov dada por
la matriz y el diagrama de transiciones a continuación:
!
1
0 1 )
P= 1 i 2
1 0 1
P= 0
0 1
A b B C f 0.01
Dado que Pij8 > 0 para todo i y j, se cumple que Pij8+n > 0 tam-
bién para todo valor de n ≥ 0. Por lo tanto, todos los elementos de
la diagonal serán estrictamente positivos a partir de P8 y siguientes
potencias, por lo que la cadena es aperiódica.
En el que !
n (1/4)n 1 − (1/4)n
P = .
0 1
A partir de esta expresión, se tiene que según n → ∞ la matriz
Pn tenderá a !
n 0 1
P → ,
0 1
lo que significa que el sistema tenderá al vector (0, 1).
Definición de π
Sea una cadena de Markov con matriz de transiciones P donde,
a partir de un valor de n, el vector de probabilidades de estado π (n)
no varía. En estas condiciones, se cumple que
π ( n ) = π ( n +1) , n1
Aplicando las ecuaciones de Chapman-Kolmogorov a ambos
lados de la equación, resulta
π (0) P n = π (0) P n +1
que puede expresarse como
π (0) P n = π (0) P n P
esto es
π (n) = π (n) P. (4.4)
Por lo tanto, si un vector π (n) no cambia a partir de un valor
de n, debe cumplir la relación dada por (4.4).8 Este vector recibe 8
De la expresión (4.4) también se tiene
el nombre de distribución estacionaria de la cadena de Markov y se que dicho vector es un autovector de la
matriz P, de autovalor la unidad.
representa sin superíndice
π = lı́m π (n)
n→∞
Ejemplo 4.27. Para el caso del modelo del tiempo, con la siguiente
matriz P !
0,6 0,4
P=
0,3 0,7
Se puede comprobar que el siguiente vector
π = (3/7, 4/7).
cumple las condiciones dadas por (4.5) y (4.6), por lo que es una
distribución de estados estacionaria (más adelante se abordará el
cálculo del vector π).
Convergencia a un único π
A partir de la definición de π, en una cadena puede ocurrir
tanto que existan varios vectores que cumplan dicha definición,
como que no exista ninguno. Además, también se ha visto que
π (n) puede aproximarse a dicho π según n → ∞, pero no en qué
condiciones: la unicidad, existencia y convergencia a π dependen
de la irreducibilidad y periodicidad de la cadena.
π a = (1/2, 1/2, 0) y
πb = (0, 0, 1),
0.5
Pr( G | C ) = 0.9
Pr( G | S) = 0.5
πP = π
πC + πS = 1. (4.9)
cadenas de markov de tiempo discreto 97
πC = 5πS ,
πS = 1/6
y, por lo tanto
πC = 5/6.
esto es,
9 5 1 1 5
Pr( G ) = · + · = .
10 6 2 6 6
1
E[nCS ] = = 10 .
1 − 0.9
esto es, se tiene en cuenta tanto el paso directo como todos los
demás posibles siguientes estados tras abandonar si , y se calcula el
valor de E[nij ] dada esta condición.
La probabilidad de que partiendo de si el siguiente salto sea sk
es, por definición, pik . El número medio de saltos para llegar desde
si a s j si el siguiente salto es un estado intermedio sk se puede
expresar como la suma de dos componentes:
o bien
E[nij ] = 1 + ∑ pik · E[nkj ]. (4.12)
sk
cadenas de markov de tiempo discreto 99
0.1
I1U
0.8 0.1
0.1 0.1
0.1
* 2
0.8 8 3 j 0.7 f 0.2
π ( n +1) = π ( n ) P = π (0) P n
Problemas
Solución. 4/19.
Solución. 8.
1/3 2/3
! !
2/3 8 Aa Be 1/2 1/3 8 Aa B
1/2 1
102 una introducción amable a la teoría de colas
Problema 4.7. (Ext. 13/14) Una tarjeta de red tiene tres veloci-
dades de transmisión, 1, 4 y 8 Mbps, que dan lugar a una proba-
bilidad de pérdida de trama de p1 = 1/2, p4 = 1/2 y p8 = 1/4,
respectivamente. El esquema que se usa para adaptar la veloci-
dad de transmisión es el siguiente: ante una pérdida, se transmite
a 1 Mbps, mientras que tras dos éxitos consecutivos a una veloci-
dad se aumenta la velocidad al siguiente valor superior disponible.
Calcule la velocidad media (en Mbps) de transmisión.
Problema 4.8. (Ej. 14/15) Sea una red compuesta por tres nodos
(A, B y C) que comparten el medio según un esquema de paso de
testigo que resulta en el siguiente patrón de transmisiones: tras
la transmisión de una trama, la estación A mantiene el testigo (y
vuelve a transmitir) con probabilidad p, y con probabilidad 1 − p
lo pasa a la estación B; la estación B siempre transmite dos tramas
seguidas antes de pasar el testigo a la estación C; la estación C
transmite una trama el 50 % de las veces, y tres tramas seguidas
el otro 50 % de las veces, antes de pasar el testigo a la estación A.
Calcule el valor de p que proporciona el 50 % del ancho de banda
disponible a la estación A.
Solución. 3/4
Problema 4.9. (*) El problema del gato y el ratón. Hay cinco cajas
en fila, con un gato en la primera y un ratón en la última. Tras un
cadenas de markov de tiempo discreto 103
Solución. 30 %
Solución. 2/3
Solución. 15 minutos.
Solución. 4/9.
1 .
Bien (1/λ) n Mal (1/µ)
1
105
106 una introducción amable a la teoría de colas
Definición
j
i
0 ≤ t 1 ≤ t 2 ≤ . . . t n −1 ≤ s ≤ t
Tx
x
0 s s+t r
1 pl
( )
Estados: Grave OK Leve
i h
pg 1
Tiempos: 1/µ g 1/λ 1/µ
1 1 1 1
$ $ $
Estados: 1 2 3 4 .! . .
Definición alternativa
Como se ha visto en los ejemplos anteriores, una cadena de Mar-
kov de tiempo continuo se puede relacionar con un diagrama de
estados que guarda una notable relación con las cadenas de Markov
de tiempo discreto. A continuación se formaliza esta relación:
1 Pr(tv <ts )
& %
Estados: 0 f 1 e 2
Pr(ts <tv ) 1
Tiempos: 1/λ 1/(λ + µ) 1/µ
dada por4 4
Comparación de variables aleatorias
exponenciales, página 42
λ µ
Pr(tv < ts ) = , Pr(ts < tv ) =
λ+µ λ+µ
λ µ
Tasa de 1 a 2: (λ + µ) · = λ y tasa de 1 a 0: (λ + µ) · = µ,
λ+µ λ+µ
π (n+1) = π (n) P.
1
Ejemplo 5.5. Para el caso de la máquina que se estropea (Ejem- '
plo 5.1), con el diagrama de estados indicado al margen, resulta Estados: OK KO
g
claro que el sistema alterna entre dos estados, y que el tiempo de 1
permanencia en cada uno de ellos se distribuye según una variable Tiempos: 1/λ 1/µ
aleatoria exponencial, de distinta media. Una posible realización de
dicha cadena sería la ilustrada en la siguiente figura:
X(t)
{t1 , t3 , t4 } ⇠ exp( )
OK
{t2 , t4 } ⇠ exp(µ)
KO
t1 t2 t3 t4 t5 t
1 Pr(tv <ts )
& %
Estados: 0 f 1 e 2
Pr(ts <tv ) 1
Tiempos: 1/λ 1/(λ + µ) 1/µ
v0 = λ
v1 = λ + µ
v2 = v2
De 0 a 1 = λ De 1 a 0 = µ
De 1 a 2 = λ De 1 a 2 = µ
qii = −vi
114 una introducción amable a la teoría de colas
1 Pr(tv <ts )
Por una parte, la media de los tiempos exponenciales de perma- $ %
nencia en cada estado. 0 d 1 e 2
Pr(ts <tv ) 1
Por otra parte, una cadena de Markov discreta con las probabili-
1/λ 1/(λ + µ) 1/µ
dades de transición entre estados10
10
Que se conoce como cadena embebida
También se ha visto que la ecuación que regula el comportamien- y donde se cumple pii = 0.
to de la cadena para cada estado i
p , [ p1 , p2 , . . . , p K ].
pi vi = ∑ p j q ji , i = 0, 1, . . . , K (5.5)
j 6 =i
pi vi
0 = p·Q .
∑ pi = 1. (5.6)
i
0 = − pOK λ + pKO µ
pOK + pKO = 1
µ µ
Con solución pOK = λ+µ y, por lo tanto, pKO = λ+µ .
p0 λ = p1 µ µ µ
p2 µ = p1 λ
p0 + p1 + p2 = 1
dos, página 97
que la cadena está en un estado i hasta que alcanza un estado j se
hace uso de la esperanza condicional.15 15
En el caso discreto, el número medio
Sea mij la esperanza de dicho tiempo. Dado que la cadena per- de iteraciones desde un estado si hasta
otro s j se podía expresar como
manece en el estado i en media un tiempo 1/vi y pasa al estado j
nij = 1 + ∑ Pik nik .
con probabilidad pij , por la ley de la probabilidad total se tiene que k6= j
1
vi k∑
mij = + pik · mkj ,
6=i,j
120 una introducción amable a la teoría de colas
2
Ejemplo 5.14. Sea el caso de la cadena representada al margen, de + 2
S k
3
K
1
la que se puede obtener la siguiente matriz de tasas de transición
entre estados (recuérdese que vi = ∑ j qij ): 2
1 4 2 3
−5 2 2 1
3 −6 3 0 s 2
Q=
4 3
2 −4 2
0
4 0 0 −4
Con estos valores, para calcular m14 se puede plantear el siguien-
te sistema de ecuaciones
1 2 2
m14 = + m24 + m34
5 5 5
1 3 3
m24 = + m14 + m34
6 6 6
1 2
m34 = + m24
4 4
del que se obtiene que m14 = 8/9.
pi vi = ∑ p j q ji , ∑ pi = 1.
j 6 =i
Problemas
Problema 5.1. (Ej. 12/13) Sea una pequeña gasolinera con dos
surtidores en serie, en la que los coches usan el surtidor más cer-
cano a la salida siempre que esté disponible, ya que un coche en
el primer surtidor bloquea el acceso al segundo surtidor. No hay
sitio para más de dos coches y tampoco espacio para esperar a que
alguno quede libre. Suponga que llegan coches a la gasolinera se-
gún un proceso de Poisson de media 1 coche por minuto y que el
tiempo en repostar se puede modelar con una variable aleatoria
exponencial de media 15 segundos. Calcule:
Problema 5.2. Sea un edificio con dos ascensores, cada uno con
un tiempo de vida que se puede modelar con una variable aleatoria
exponencial de media 1/λ. Hay dos políticas de reparación:
Solución. 1/4
Problema 5.6. (Ord. 15/16) Sea un sistema con dos servidores sin
espacio en cola. Un servidor tiene una capacidad de 2 paquetes/s
y el otro 4 paquetes/s. Los paquetes llegan según un proceso de
Poisson a tasa 1 paquete/s y son atendidos por el servidor rápido
si está disponible (vacío), si no, por el servidor lento, y si los dos
servidores están ocupados, son descartados. En estas condiciones:
Calcule la proporción de paquetes descartados. ¿Qué proporción
de paquetes son atendidos por el servidor rápido y qué propor-
ción por el lento?
Solución. 10/3 W.
Problema 5.10. (Ext. 11/12) Sea una cafetería, pequeña, que ofre-
ce WiFi gratis a los clientes. De hecho, los clientes sólo van para
descargarse una cantidad de datos que se puede modelar según
una variable aleatoria exponencial, de media 480 Mbytes (acabada
la descarga abandonan el local). La velocidad efectiva de la WiFi es
de 32 Mbps, que se distribuye equitativamente entre los usuarios de
la cafetería (por ejemplo: con dos clientes, la velocidad de descarga
por cliente es la mitad que en el caso de un cliente solo). Si como
mucho caben 4 clientes, y llegan según un proceso de Poisson de
tasa 15 clientes/hora, ¿cuánto tiempo pasan en media los clientes
en la cafetería (en minutos)?
124 una introducción amable a la teoría de colas
Solución. 52/15.
Problema 5.12. (Ej. 11/12) Sea una red 802.11 donde la tasa de
transmisión es de 4 Mbps. Una estación 802.11 debe primero au-
tenticarse y luego asociarse (en este orden) antes de poder enviar
datos. Suponga que autenticarse requiere un tiempo exponencial de
media 1 ms y asociarse supone otro tiempo exponencial de media 1
ms, pero este último proceso falla un 25 % de las veces, lo que con-
lleva además la pérdida de la autenticación. Una vez completada la
asociación, la estación transmite durante un tiempo exponencial de
media 8 ms, pasado el cual vuelve al estado inicial (esto es, sin au-
tenticar ni asociar). Calcule la tasa máxima efectiva de transmisión.
Solución. 3 Mbps.
Definición
127
128 una introducción amable a la teoría de colas
1 k
T = lı́m ∑ T (k)
k→∞ k 1
medio de servicio:
T = W + ts .
Dado un tiempo medio de servicio ts también se puede definir
una tasa (máxima) de servicio µ = 1/ts , que se corresponde con
el ritmo al que los usuarios “salen” de un recurso si éste siempre
se encontrase ocupado. Por lo tanto, la expresión anterior también
puede escribirse como
1
T=W+ .
µ
4. La cola tiene una capacidad máxima de dos usuarios, dado que Figura 6.4: Sistema D/G/2/4
el sistema puede albergar cuatro usuarios en total (4).
4. La longitud máxima de la cola puede suponerse ilimitada, dado Figura 6.5: Sistema M/D/3/∞
que la capacidad del sistema es infinita (∞).
A/B/m/K/N/Z
Teorema de Little
N ( t ) = α ( t ) − β ( t ).
0
(α(τ ) − β(τ )) dτ ≈ ∑ Ti
i =1
α(t)
λ , lı́m
t→∞ t
N = λ·T
Q = λ·W
Por otro lado, la ocupación media del recurso ρ viene dada por
la tasa de entrada y el tiempo medio de servicio ts (o su inversa
µ), esto es
λ
ρ = λ · ts =
µ
λ · T = λ · W + λ · ts
N = Q + ρ.
y, por lo tanto,
N = Q+m·ρ .
El sistema M/M/1
p1 ( λ + µ ) = p0 λ + p2 µ (6.5)
p1 ( λ + µ ) = p1 µ + p2 µ
pn λ = pn+1 µ, (6.6)
p n = ρ n p0 .
con solución ! −1
∞
p0 = ∑ρ n
.
n =0
Dado que se trata de una serie geométrica, para que p0 tenga
solución es preciso que ρ < 1. De esta forma, se tiene que8 8
Expresión para la suma infinita:
∞
( 1
1−ρ Para n = 0 ∑ ρi = 1−ρ
pn = n i =0
ρ (1 − ρ ) Para n ≥ 0
Ejemplo 6.5. Sea un cajero al que llegan clientes según una tasa
de 10 clientes/hora. El tiempo medio que un cliente pasa en el
cajero se puede modelar como una variable aleatoria exponencial
de media cuatro minutos. Se pide: calcular la probabilidad de que
el cajero esté vacío, y de que haya más de un cliente esperando.
Según los datos, se tiene que:
10 clientes/60 minutos 10
ρ= = = 2/3.
1 cliente/4 minutos 15
teoría de colas: sistemas básicos 137
p0 = 1 − ρ = 1/3
Sobre el significado de ρ
El parámetro ρ se define como el cociente entre la tasa de lle-
gadas al sistema y la tasa máxima de salida que proporciona el
servidor
λ tasa llegada
ρ= = ,
µ tasa salida
lo que también puede interpretarse como el tiempo medio de servi-
cio entre el tiempo medio entre llegadas
1/µ tiempo servicio
ρ= = .
1/λ tiempo entre llegadas
Por lo tanto, el hecho de que ρ < 1 para que el sistema tenga
una solución resulta muy coherente: si ρ > 1, se tendría que la tasa
media de llegada al sistema es mayor que la tasa máxima de salida
(o que el tiempo medio para servir un usuario es mayor que el
tiempo medio entre llegadas), por lo que el sistema no sería capaz
de cursar la carga de trabajo que se le presenta. Dado que se trata
de una cola M/M/1/∞, la longitud de la cola crecería de forma
indefinida, por lo que el número de usuarios en el sistema tendería
a infinito.
De esta forma, en un sistema sin rechazo donde el número má-
ximo de usuarios no está ilimitado, si la tasa de llegadas es mayor
que la tasa agregada de salida, el sistema se encontrará conges-
tionado por lo que no tiene sentido realizar un modelado de sus
prestaciones. Cuando el sistema sí rechaza usuarios (por ejemplo,
el caso de la gasolinera del Ejemplo 5.4, página 109, que admitía un
número máximo de coches) la condición ρ < 1 no resulta necesaria,
dado que el número de estados de la cadena de Markov es finito.
N 1/µ
T= =
λ 1−ρ
Ejemplo 6.6. Sea el caso del cajero del Ejemplo 6.5, donde se tenía
que ρ = 2/3. El número medio de usuarios en el sistema se puede
calcular como
2/3
N= = 2 usuarios.
1 − 2/3
Mientras que el tiempo medio de estancia en el sistema es
ts 4
T= = = 12 minutos.
1−ρ 1/3
ρ = 12/15 = 4/5,
ts 4
T= = = 20 minutos.
1−ρ 1/5
Q ρ1/µ
W= =
λ 1−ρ
ts
W = T − ts = − ts ,
1−ρ
Ejemplo 6.7. Sea una línea de transmisión a 100 Mbps, a la que lle-
gan tramas de una longitud que puede modelarse con una variable
aleatoria exponencial de media 1500 octetos. El tiempo entre tramas
es otra variable aleatoria exponencial de media 0.18 ms. Bajo estas
suposiciones, se quiere calcular el retardo medio por trama y el
tiempo medio de espera en cola.
Dado que las tramas tienen una longitud exponencial10 y la 10
Suponer que la longitud de una
trama (un número entero) se puede
velocidad de la línea es constante, el tiempo de transmisión de cada
modelar con una variable aleatoria
trama será también una variable aleatoria exponencial, de media continua será menos exacto a medida
de la longitud de las tramas sea menor
y, por tanto, mayor sea el error al
ts = 1500 B · 8/100 Mbps = 120 µs,
redondear al siguiente entero.
ts 120
ρ= = = 2/3,
1/λ 180
Relación entre N, T, W y Q
Usuarios Tiempos
×1/λ
ρ . 1/µ 1
Sustema: N= 1− ρ T= 1− ρ = µ−λ
K
+ρ −1/µ
ρ2 1/µ·ρ
Cola: Q= 1− ρ m W= 1− ρ
×λ
FW (t) = 1 − ρe−(µ−λ)t .
Ejemplo 6.8. Volviendo al ejemplo 6.5 del cajero, donde los usua-
rios llegan a una tasa de λ = 10 clientes/hora y el tiempo medio de
servicio es ts = 4 minutos. La carga del sistema y el retardo medio
son, respectivamente,
2
ρ= y T=12 minutos ,
3
por lo que el tiempo medio de espera en cola es W=12-4=8 minu-
tos. La probabilidad de que un usuario esté más de t unidades de
tiempo esperando a usar el cajero vendrá dada por
1 − FW (t) = ρe−(µ−λ)t ,
Fρ (t) = 1 − e−µt .
F (t) = 1 − e−λt
El sistema M/M/m
λ λ λ λ λ λ λ λ
% % % % % %
0 1 2 3 . . .a m-1 m m+1 .. .
e e e e e e e
µ 2µ 3µ 4µ ( m −1) µ mµ mµ mµ
λ n−m
pn = pm , n ≥ m
mµ
que, sustituyendo pm por su valor según (6.9), queda como
λ n−m λ m 1 λ n mm
pn = p0 = p0 , n ≥ m (6.10)
mµ µ m! mµ m!
Antes de continuar con el análisis de la Cadena de Markov, con-
viene detenerse en los dos siguientes términos que aparecen en
(6.9) y (6.10):
λ λ
ρ, , I,
mµ µ
que, obviamente, se relacionan mediante la expresión I = mρ.
Los términos ρ e I
Por una parte, el término ρ se define como el cociente entre la
tasa de entrada λ y la tasa máxima de salida con todos los servido-
res ocupados mµ. Por lo tanto, dado que la capacidad de la cola es
infinita, para que se pueda obtener una solución del sistema será
necesario que se cumpla (de forma similar al sistema M/M/1)
λ < mµ → ρ < 1 .
144 una introducción amable a la teoría de colas
N = λts = λ/µ = mρ ,
∞
!
m −1 n m
I nm
p0 ∑
n! n∑
+ ρ =1
n =0 =m m!
∞ ∞ ∞
N= ∑ npn
mm mm
∑ (n − m) pn = ∑ (n − m)ρn m! p0 = ρm m! p0 ∑ (n − m)ρn−m
0
Q=
n=m n=m n=m
146 una introducción amable a la teoría de colas
lo que lleva a
Im ρ
Q= p0 (6.12)
m! (1 − ρ)2
λ = 2 usuarios/segundo
µ = 2 usuarios/segundo
λ ρ 1
I= = 1, ρ= =
µ m 2
Im · ρ 1 · 1/2 1
Q= 2
p0 = 2
· = 1/3 ,
m!(1 − ρ) 2!(1 − 1/2) 3
Q 1 1 2
W= = segundos, yT=W+ = segundos .
λ 6 µ 3
m −1
1 1 2
Pr(No esperar) = ∑ = p0 + p1 = + =
3 3 3
.
n =0
teoría de colas: sistemas básicos 147
Relación entre PQ y Q
Resulta destacable que las expresiones para PQ y Q, dadas por
(6.11) y (6.12), guardan la siguiente relación17 17
Por comodidad, se repiten las
expresiones aquí:
ρ
Q= P Im 1
1−ρ Q PQ =
m! 1 − ρ
p0
Im ρ
Dicha relación puede deducirse aplicando la esperanza condi- Q= p0
m! (1 − ρ)2
cionada para el cálculo de Q, según se tenga que esperar o no al
sistema:
Q = E[ Q] = E[ Q | Esperar] PQ + E[ Q | No esperar](1 − PQ )
E[ Q] = E[ Q | Esperar] PQ
λ λ λ λ
& & &
m m+1 m+2 m+3 .. .
f f f g
mµ mµ mµ mµ
λ 1
ρ= = ,
µ 2
1/µ
T= = 1/2 segundo,
1−ρ
Utilización de recursos
En un sistema M/M/m (incluyendo m=1) el término ρ es el
cociente entre la tasa de llegadas y la tasa máxima de salidas
λ
ρ= ,
mµ
y coincide, como se vio en Ejemplo: Aplicación de Little para un
sistema con un recurso (página 133), con la utilización media de un
recurso. Sin embargo, en un sistema con rechazo es preciso tener en
cuenta la tasa efectiva de llegadas:
λ = λ(1 − PB ) .
ρ · m · µ.
N = λ · T = λ(1 − PB ) · T.
Ejemplo 6.13. Sea una gasolinera similar a la del Ejemplo 5.4, con
un surtidor y una capacidad máxima para dos coches (incluyendo
al que está repostando). La gasolinera siempre está llena y el tiem-
po medio de estancia es de 5 minutos. En estas condiciones, la tasa
de coches que entran a la gasolinera será Figura 6.18: Gasolinera con un surtidor
y sitio para dos coches.
N 2
λ= = = 24 coches/hora.
T 5
Si se estima que la tasa de coches que quieren entrar a la gasoli-
nera es de 30 coches/hora, la probabilidad de rechazo es del 20 %.
teoría de colas: sistemas básicos 151
El sistema M/M/1/K
Las relaciones entre estados son las mismas que para el caso del
M/M/1, es decir
n
λ
pn = p0 , ∀1 ≤ n ≤ K,
µ
Empleando el parámetro I = λ/µ (que no coincide con el pa-
rámetro ρ, según se verá más adelante), las relaciones se pueden
expresar como
pn = I n p0 , ∀1 ≤ n ≤ K,
A diferencia del M/M/1, calcular el valor de p0 hay que hacer
una suma finita
K K
∑ pn = ∑ I n p0 = 1
n =0 n =0
quedando la expresión para p0 como
! −1
K
p0 = ∑ In (6.13)
n =0
1 − IK
λ = λ (1 − p K ) = λ
1 − I K +1
152 una introducción amable a la teoría de colas
que queda
I ( K + 1 ) I K +1
N= − ,
1−I 1 − I K +1
A partir de N se puede obtener T aplicando el teorema de Little
N
T= ,
λ (1 − p K )
W = T − ts ,
W
Q=
λ (1 − p K )
I ( K + 1 ) I K +1 2 (4 + 1)24+1 98
N= − = − =
1−I 1 − I K +1 1−2 1 − 24 + 1 31
por lo que el tiempo medio para imprimir es
N 98/31 98
T= = = minutos (78.4 s)
λ (1 − p K ) 5(1 − 16/31) 75
( K + 1) p0 = 1
λ = 2,5 peticiones/minuto.
El sistema M/M/m/m
Ejemplo 6.16. Para una población que genera llamadas a una tasa
de 4 llamadas/minuto (de Poisson) se instala una centralita con
dos circuitos. La duración de una llamada se puede modelar con
una variable aleatoria exponencial de media 30 segundos. En estas
condiciones, se tiene que
4
λ = 4 llamadas/minuto, µ = 2 llamadas/minuto, I = =2.
2
23
3! 4
pm = 2 = ,
23 19
1 + 2 + 22! + 3!
m (∆m) pm (∇ pm ) p m − p m −1
2 0.400
3 (50 %) 0.211 (52 %) -0.189
4 (33 %) 0.095 (45 %) -0.116
5 (25 %) 0.037 (39 %) -0.061
T = W + ts
N = λ·T
λ λ
I= , ρ=
µ µ
En un sistema M/M/1:
1/µ 1
p n = ρ n (1 − ρ ), T= =
1−ρ µ−λ
FT (t) = 1 − e−(µ−λ)t .
En un sistema M/M/m:
! ! −1
m −1 n
I Im 1 Im · ρ
p0 = ∑ n! + m! · 1 − ρ , Q=
m!(1 − ρ)2
p0 .
n =0
n
I
· p0 Si n ≤ m
pn = n!
m
ρn m · p
Si n ≥ m
0
m!
Im
m!
PQ = Ec (m, I ) =
−1 I n Im
(1 − ρ ) ∑m
n=0 n! + m!
En un sistema M/M/1/K:
n
1− λµ λ
( K +1 ) I K +1
µ I
Si λ 6= µ pn = K +1 N= 1− I − 1 − I K +1
1− λµ
1 K
Si λ = µ pn = K +1 N= 2
En un sistema M/M/m/m:
! −1
m
In In
p0 = ∑ n!
pn =
n!
p0
n =0
teoría de colas: sistemas básicos 157
Problemas
Solución. 1. 16/31; 2. 1’
Hay usuarios con mayor prioridad que otros, por lo que cuando
distintos tipos de usuarios coinciden en la cola, el de mayor
prioridad tendrá preferencia para ser atendido. Esto puede servir
para modelar un router que proporcione “diferenciación de
servicio” entre tipos de trama, p.ej., si las tramas de un usuario
premium tienen prioridad sobre las de un usuario normal. Este
caso se analizará con el sistema M/G/1 con prioridades.
El sistema M/G/1
161
162 una introducción amable a la teoría de colas
Planteamiento básico
Dado que los tiempos de servicio no siguen una variable alea-
toria exponencial, el sistema no puede modelarse con una cadena
de Markov, como los sistemas básicos. Dado que las llegadas son
de Poisson, para analizar el sistema se aplicará la propiedad PAS-
TA (página 55): la esperanza de lo que “ve” un usuario al llegar al
sistema coincide con la media temporal de la variable considerada
(Poisson Arrivals See Time Averages).
Sea una llegada cualquiera al sistema. Lo dicha llegada “ve” que
tiene que esperar antes de llegar al recurso (ver Figura 7.1) se puede Figura 7.1: Estado visto por una
dividir en dos componentes: llegada al sistema
W = Q · ts + R
W = λ · W · ts + R .
T = W + ts = 0.36 ms.
ρ · ts
W= ,
(1 − ρ )
1 ρ · ts
W= · ,
2 (1 − ρ )
esto es, la mitad que para el caso del M/M/1. Estos resultados
confirman que cuanto mayor es la variabilidad en el tiempo de
servicio, peores serán las prestaciones que recibirán los usuarios.
teoría de colas: sistemas avanzados 167
por lo que, dadas las tasas de llegadas de todos los tipos de flujo
{λk }, la probabilidad del tipo i se puede calcular como la propor-
ción de dicho flujo sobre el total
λi
αi =
∑1N λi
N
E[t2s ] = ∑ αi · E[t2i ] ,
i =1
λE[t2s ]
Wi = ∀i
2(1 − ρ )
Ti = W + ti ,
λE[t2s ]
W= = 11 min.,
2(1 − ρ )
por lo que el tiempo medio para pasar el control un viajero frecuen-
te es
f req
T f req = W + ts = 11,5 min.,
mientras que para un viajero no frecuente es
no f req
T no f req = W + ts = 14 min.
Q1 = λ1 W1 ,
W2 = R + Q1 · t1 + Q2 · t2 + λ1 · W2 · t1 ,
W2 = W1 + Q2 · t2 + λ1 · W2 · t1 .
Tk = Wk + tk .
Redes de colas
N = N1 + N2 ,
T = T1 + T2 ,
λ /A /B /D λD
/
p ab ?
1− p ab pcd
C /
1− pcd
λ D = λp ab + λ(1 − p ab ) pcd
ρa = λa ta , ρb = λb tb , ρc = λc tc , ρd = λd td
donde
λ a = λ, λb = λ a p ab , λc = λ a (1 − p ab ), λd = λp ab + λ(1 − p ab ) pcd
p ab
λ /A /B / /
?C
D /E /
pde
µ = 1/ts = 50 u/s.
M/M/1:
Na = 4, Nb = 3/2, Nc = 7/3, Ne = 1/9 . ρ
N= , con ρ = λ/µ .
1−ρ
El sistema D se trata de un M/M/m, con una probabilidad de
estar vacío y número medio de usuarios en cola igual a11 En un sistema M/M/m, el número
11
lo que lleva a que el número medio de usuarios en el sistema D es donde I = λ/µ y ρ = I/m.
197 1
Nd = λ · T = ≈
1960 10
Por lo tanto, el número medio total de usuarios en la red es
1448 362
N= ∑ Ni = 180
=
45
≈ 8 usuarios,
λ −1 t s .
Por cada por cada petición que llegue al sistema se genera una
ráfaga de llegadas a la cola, separadas entre sí el tiempo de servicio
de la llegada original. Este patrón a ráfagas incumple claramente
las propiedades de incrementos estacionarios e independientes, por
lo que el proceso de llegadas a la cola no será de Poisson, así que el
sistema no puede analizarse partiendo del M/M/1.
A diferencia del caso de las redes acíclicas, en una red cíclica, en
general, no se podrá suponer que los procesos de llegada sean de
Poisson. Sólo cuando se puedan hacer algunas suposiciones, orien-
tadas a que la naturaleza “a ráfagas” de las llegadas se debilite,
se podrá analizar el comportamiento de una red de colas partien-
do del análisis de cada cola por separado –consideraciones que se
verán a continuación.
N
λi = ∑ λ j p ji + r j (7.8)
j=1,j6=i
λ1 = λ3 + λ
λ3 = λ2 p23 .
λ2 = λ1 .
178 una introducción amable a la teoría de colas
λ
λ1 = λ1 p23 + λ → λ1 =
1 − p23
N
psj = 1 − ∑ p jk > 0 ,
k =1,k 6= j
λ2 = λ1 p12 + λ4 p42 ,
λ4 = λ3 = λ1 (1 − p12 )
teoría de colas: sistemas avanzados 179
λ 8
λA = = = 10 tramas/ms.
1− p 1 − 0,2
N = NA + NB = 3.
Esta hipótesis puede resultar algo más discutible, ya que las tra-
mas pertenecientes a un mismo flujo siguen el mismo camino desde
el origen al destino.13 Si se trata de un agregado de varios flujos, 13
Salvo que aparezca algún tipo de
cada uno con un destino diferente, cuanto mayor sea la variedad mecanismo de balanceo de carga o las
rutas cambien durante un flujo.
de destinos y más mezcladas estén las tramas, más razonable será
realizar esta suposición.
λ1
/+ / 40 Mbps /. /
O
p=1/4 p=1/4
λ2
/ 40 Mbps /. /+ / 40 Mbps /
1
λ1 + · λ2 = 4 tramas/ms,
4
lo que supone una ocupación relativamente alta, ρ = λ/µ = 4/5,
por lo que, por la aproximación de Kleinrock, también podría anali-
zarse como un sistema tradicional.
Por último, el segundo enlace inferior recibe el 75 % del flujo λ2
tras pasar por un enlace anterior, y el 25 % del flujo del anterior
enlace. Aún suponiendo que el routing fuese aleatorio, en valores
184 una introducción amable a la teoría de colas
∑iK=1 λi E[t2i ]
1
2
Wk =
(1 − ρ1 − . . . − ρk−1 )(1 − ρ1 − . . . − ρk )
Problemas
Solución. 2090/9 µs
p=1/2
λ1
/ 40 Mbps /
8
p=1/2
p=1/4 &
λ2
/ 80 Mbps / 80 Mbps /
p=3/4
Solución. 1. 1 s; 2. 5/17
Problema 7.9. (Ord. 15/16) Sea una red de tres colas en paralelo.
Cuando llega una trama, con probabilidad 1/3 va a un sistema
M/M/1 con una tasa de servicio de 8 paquetes/s y abandona la
red; con probabilidad 1/6 va a un sistema M/M/2 donde cada
servidor opera a una tasa 3 paquetes/s y abandona la red; en el
resto de casos va a un sistema M/M/1/1 donde el servidor opera a
una tasa 24 paquetes/s. En el tercer subsistema, los paquetes que se
encuentran el sistema lleno se tiran. Si el proceso de llegadas es de
Poisson a tasa 18 paquetes/s, calcule:
Solución. 0.296 s
Se tiene que:
Se pide: