Capítulo 7

Fenómenos de Espera

7.1. Preliminares

En este capítulo estudiaremos el comportamiento (estocástico) de sistemas de espera, entendidos

como aquellos que involucran un flujo de individuos/entidades que deben ser procesados por un
conjunto de servidores de acuerdo a algún protocolo de atención. Dada su aplicación en, por
ejemplo, el modelamiento de sistemas de atención (e.g. espera en una sucursal de un banco o en
un call-center), nos interesa analizar medidas de desempeño tales como tiempos promedios de
estadía en el sistema, largo promedio de las colas, etc.

El elemento base de un sistema de espera es la cola simple, las que serán descritas utilizando la
notación de Kendall, que especifica seis elementos.

Definición 7.1. Notación de Kendall

Describiremos una cola como una tupla A|B|C|D|E|F , donde A describe el proceso de llegada
de entidades, B la distribución de tiempos de servicio, C el número de servidores, D denota
la capacidad máxima del sistema (por defecto ∞), E el tamaño de la población (por defecto
∞), y F la disciplina de atención.

Para la especificación de A y B se hace referencia a la distribución del tiempo entre llegadas/-

tiempo de antención, respectivamente. Por ejemplo, A=M denota que el tiempo entre llegadas
tiene la propiedad de Markov, es decir, las llegadas constituyen un proceso de Poisson. De la
misma forma A=D denota que los tiempos entre llegadas son Deterministas y B=G denota
una distribución General.

Los valores de C, D y E son enteros no negativos y F denota la disciplina utilizada por los
servidores para priorizar la atención de las entidades. Por ejemplo F=FIFO denota la disciplina
donde las entidades son atendidas de acuerdo al orden de llegada y F=LIFO denota aquella

173
donde la última entidad en llegar es la primera en ser atendida.

Para propósitos del curso, estamos interesados en filas que pueden ser representadas mediante
cadenas de Markov en tiempo continuo. La notación de Kendall es versátil, pero de ninguna
forma pretende cubrir todas las posibles configuraciones posibles para una fila simple.

Ejemplo 7.1. La fila M/M/1

Este sistema corresponde a una fila donde un solo servidor demora en atender entidades un
tiempo aleatorio de distribución exponencial, y las entidades llegan al sistema de acuerdo a
un proceso de Poisson. Denotando λ a la tasa del proceso de Poisson y µ al inverso del tiempo
esperado de atención, tenemos que el modelo de cadena de Markov correspondiente a la cola
M/M/1 admite la siguiente representación gráfica.

λ λ λ

0 1 2 ···
µ µ
µ

Desde el capítulo anterior sabemos que el vector de probabilidades estacionarias π = (π(1), π(2), . . .)
es tal que
π(i) = ρi (1 − ρ), i ≥ 0,

donde ρ = λ/µ < 1. La condición para la existencia de probabilidades estacionarias (ρ < 1)

puede interpretarse como que la persona que atiende lo hace a un ritmo más rápido del que tiene
la gente que llega.

Ejemplo 7.2. La fila M/M/∞

La fila M/M/∞. Este sistema corresponde a un autoservicio donde las entidades demoran
un tiempo aleatorio de distribución exponencial en salir del sistema y las entidades llegan al
sistema de acuerdo a un proceso de Poisson. Denotando λ a la tasa del proceso de Poisson y
µ al inverso del tiempo esperado de atención, tenemos que el modelo de cadena de Markov
correspondiente a la cola M/M/∞ admite la siguiente representación gráfica.

λ λ λ

0 1 2 ···
µ 3µ
2µ

Desde el capítulo anterior sabemos que el vector de probabilidades estacionarias π = (π(1), π(2), . . .)
ρi −ρ
es tal qu e π(i) = i! e , i ≥ 0, donde ρ = λ/µ.

174
 Ejemplo 7.3. Fila con capacidad finita

La fila M/M/2/3. Siguiendo la lógica de los ejemplos anteriores, la cadena asociada a esta
fila admite la siguiente representación gráfica.

λ λ λ

0 1 2 3
µ 2µ
2µ

7.2. Ley de Little

Estamos interesados en calcular ciertas medidas de desempeño (de largo plazo) asociadas a dis-
tintos modelos de colas. En particular, nos gustaría calcular el número promedio de entidades
y/o el tiempo promedio que pasa una entidad en el sistema, en el largo plazo. Normalmente,
una de estas cantidades es más sencilla de calcular que la otra. La ley de Little relaciona estas
dos cantidades, de forma que el cálculo de una cantidad es equivalente el cálculo de la otra.
Sorprendentemente, la ley de Little aplica a cualquier sistema de espera, independiente de su
especificación.

Teorema 7.1. Ley de Little (1961)

Considere un sistema de espera y defina los procesos (nt , t ≥ 0), (wn , n ∈ Z) y (τn , n ∈ Z),
donde nt representa el número de entidades en el sistema en el instante t, wn el tiempo que
pasa en el sistema la n-ésima entidad en llegar, y τn el tiempo entre la llegada de la n − 1-
ésima y la n-ésima entidad. Si los procesos anteriores son estacionarios y tienen media finita,
entonces, si definimos
ˆ t
1
L(ω) = lı́m ns (ω)ds
t→∞ t 0
m
1 X
W (ω) = lı́m wj (ω)
m→∞ m
j=1
n
1 X
T (w) = lı́m máx{n : τj (ω) ≤ t},
t→∞ t
j=1

entonces, con probabilidad 1, los límites de arriba existen, y satisfacen

W (ω) = T (ω) · L(ω).

Notamos que la cantidad L representa el número promedio (en el largo plazo) de entidades
en el sistema, W el tiempo promedio de estadía en el sistema y T el tiempo promedio
entre llegadas.

175
Aquí presentaremos una prueba del resultado bajo el supuesto que los limites en el enunciado
existen (los supuestos adicionales en el enunciado garantizan que esto ocurre). Obviaremos la
dependencia de las cantidades respecto a ω, entendiendose que los resultados se cumplen para
cada ω ∈ Ω.

Demostración. Sea Sn := el tiempo de la n-esima llegada, y In (t) = 1 si la n-esima

P
m≤n τm
entidad en llegar está en el sistema en el instante t, In (t) = 0 si no. Entonces,
ˆ ∞ ∞
X
wn = In (t)dt, nt = In (t),
0 n=1

Para t ≥ 0 definimos U (t) := y V (t) := n:Sn +wn ≤t wn . Es fácil ver que

P P
n:Sn ≤t wn
ˆ t
V (t) ≤ ns ds ≤ U (t). (7.1)
0

(Para ver esto, imagine que cobramos $1 por persona por unidad de tiempo: si le cobramos a las
personas en el instante en que egresan, V (t) es la ganancia acumulada al instante t; si le cobramos
´t
por unidad de tiempo, la ganancia acumulada es 0 ns ds; y si le cobramos cuando ingresan, U (t)
es la ganancia acumulado al instante t). Definimos t0 = 0 y N (t) := máx{n : Sn ≤ t}, el número
de llegadas acumuladas entre 0 y t. Dado que los τn son finitos, tenemos que N (t) → ∞ a medida
que t → ∞, y por lo tanto
N (t)
1 X
W = lı́m Wn .
t→∞ N (t)
n=1
Dado que T < ∞ y W < ∞, tenemos que
N (t)
N (t) 1 X U (t)
T W = lı́m wn = lı́m .
t→∞ t N (t) t→∞ t
n=1

U (t) V (t)
Por (7.1) basta probar que lı́mt→∞ t = lı́mt→∞ t . Puesto que T < ∞ y W < ∞, se puede
probar que Wn /Sn → 0 cuando n → ∞. Sea ϵ > 0, dado. Existe un N tal que Wn < Sn ϵ para
todo n > N . Entonces,
X X X
U (t) ≥ V (t) = wn ≥ wn + wn
n:Sn +wn ≤t n≤N :Sn +wn ≤t n>N :Sn (1+ϵ)≤t
X X X
= wn − wn + wn .
n≤N :Sn +wn ≤t n≤N :Sn (1+ϵ))≤t n:Sn (1+ϵ))≤t

Notamos que los dos primeros términos arriba están acotados por n<n wn , y por lo tanto son
P

o(t). Entonces, dividiendo por t y tomando limite, tenemos que

U (t) V (t) U (t)
lı́m ≤ lı́m ≤ (1 + ϵ)−1 lı́m .
t→∞ t t→∞ t t→∞ t
El resultado se cumple dado que ϵ es arbitrario. ■

176
 Observación 7.1. Importante

Notemos que la ley de Little se cumple para cada evento ω ∈ Ω y para cada sistema de espera
que cumple con las condiciones de arriba. Esto incluye subsistemas dentro de sistemas más
grandes (por ejemplo, el subsistema de gente esperando ser atendido en una cola M/M/1).

Normalmente utilizaremos la ley de Little en sistemas donde la llegada está dada por un proceso
de Poisson homogéneo. Por lo mismo, es común ver la ley de Little enunciada como

L = W · λ,

donde λ denota la tasa de llegada de entidades y, L y W son referidas como los valores esperados
del número promedio y tiempo promedio de estadía en el sistema.

Ejemplo 7.4. Ley de Litle para una Fila M/M/1

Para esta fila, tenemos que el número promedio de entidades en el sistema (en el largo plazo)
está dado por
X X ρ ρ λ
L= iπi = iρi (1 − ρ) = (1 − ρ) 2
= = .
(1 − ρ) 1−ρ µ−λ
i i

Por otro lado,el tiempo promedio de estadía en el sistema puede calcularse condicionando
en el número de entidades en el sistema al momento de llegada de una entidad en el largo
plazo. Esto es, asumiendo la política FIFO y denotando Te al tiempo de estadía en el sistema,
tenemos que
X
W = E[Te | i entidades al llegar] πi
i
X 1 i
= (i + 1) · ρ (1 − ρ)
µ
i
λ 1 1
= + = .
(µ − λ)µ µ µ−λ

Alternativamente, podemos calcular W utilizando Little: tenemos que el tiempo esperado de

estadía en la fila es
L 1
W = = .
λ µ−λ

Métricas adicionales. Normalmente nos interesa calcular los tiempos promedios de estadía en
el subsistema de espera y en el de servicio, y lo mismo para el número promedio de entidades.
Utilizando los subíndices q y s para denotar dichos subsistemas, tenemos que

L = Ls + Lq , W = Ws + Wq ,

donde, por ejemplo, Ls denota el número promedio de entidades en servicio, en el largo plazo. Para

177
la fila M/M/1, tenemos que trivialmente Ws = µ−1 , por lo que rápidamente vemos que
1 1 λ
Wq = − = .
µ−λ µ (µ − λ)µ
Respecto a los largos de fila, tenemos que
X
Ls = 1{i > 0}πi = 1 − π0 = ρ,
i
λ2
con lo que concluimos que Lq = λ
µ−λ − λ
µ = (µ−λ)µ . Alternativamente, podemos aplicar Little
a cada subsistema (notando que la tasa de entrada a cada uno de ellos es λ), para obtener
que
λ λ2
Ls = λ Ws = = ρ, Lq = λ Wq = .
µ (µ − λ)µ

Ejemplo 7.5. Ley de Little para una Fila M/M/∞

En esta fila, la distribución estacionaria es Poisson con tasa ρ, por lo tanto tenemos que
X ρi
L= i e−ρ = ρ,
i!
i

por lo que (usando Little) concluimos que W = L

λ = µ,
1
lo que tiene sentido, dado que este
sistema es un autoservicio. Por lo mismo, tenemos que Wq = 0, por lo que Ws = W . De la
misma forma, se tiene que Lq = 0, por lo que Ls = L.

7.3. Colas en Tandem

Considere un sistema con dos estaciones de servicio, cada una con un solo servidor. Una atención
en la estación Si demora un tiempo aleatorio de distribución exponencial de tasa µi , i ∈ {1, 2}.
Entidades llegan al primer servidor de acuerdo a un proceso de Poisson de tasa λ. Al ser atendidos,
pasan de inmediato al siguiente servidor. Las entidades esperan en cada estación por su turno
en ser atendidos.

λ S1 S2

Queremos analizar el sistema descrito arriba, idealmente caracterizando su comportamiento en

estado estacionario y encontrando expresiones para métricas tales como el tiempo esperado de
estadía en el sistema, número promedio de entidades en el sistema, etc. El sistema en sí mismo,
puede ser modelado como una cadena de Markov en tiempo continuo, donde un estado es
un par ordenado (n1 , n2 ) donde ni representa el número de entidades en la estación Si , i ∈ {1, 2}.

Denotemos a π = (π(n1 , n2 ) : ni ≥ 0, i = 1, 2) como el vector de probabilidades estacionarias, y

definimos πi a la distribución marginal del número de entidades en el sistema i en el largo plazo.
Claramente, tenemos que
π1 (n) = ρn1 (1 − ρ1 ), n ≥ 0,

178
donde ρ1 = µ1 .
λ
Esto, debido a que si ignoramos la segunda estación, el primer servidor corres-
ponde a una fila M/M/1. A priori, el cálculo de la marginal π2 no es directo, debido a que no
conocemos las características del proceso de llegada de entidades al segundo servidor. El siguien-
te resultado, sin embargo, nos dice que en estado estacionario dicho proceso de llegada es
Poisson de tasa λ, con lo que la marginal π2 está dada por

π2 (n) = ρn2 (1 − ρ2 ), n ≥ 0,

donde ρ2 = µ2 .
λ

Lema 7.1. S. Ross - Lemma 5.6.2

Considere una fila M/M/C. Si λ < C µ (condición de estado estacionario), entonces el proceso
de salida de entidades, en estado estacionario, es un proceso de Poisson de tasa λ.

Demostración. Argumentamos por reversibilidad. De la representación gráfica de la cadena aso-

ciada a la fila M/M/C vemos que este corresponde a un proceso de nacimiento y muerte y, por
lo tanto, dicha cadena es reversible. En la cadena reversa, el proceso de llegada de entidades, en
el largo plazo, corresponde a un proceso de Poisson de tasa λ (por reversibilidad). Sin embargo,
interpretado desde el punto de vista del proceso original, este proceso corresponde a las salidas
de entidades desde la fila. Concluimos que las salidas en estado estacionario forman un proceso
de Poisson de tasa λ. ■

Con este resultado, tenemos que podemos calcular las distribuciones marginales del número
de entidades en cada servidor, en estado estacionario. Estas distribuciones, sin embargo, no nos
permiten a priori calcular el vector π, debido a la posible correlación entre el número de entidades
en cada estación. El siguiente resultado nos muestra que, en estado estacionario, los números
de entidades en cada subsistema son variables aleatorias independientes. Con esto podremos
recuperar el vector π a partir de π1 y π2 , para obtener (sujeto a que ρi < 1, i ∈ {1, 2})

π(n, m) = ρn1 (1 − ρ1 ) ρm
2 (1 − ρ2 ), m, n ≥ 0,

Lema 7.2. S. Ross - Lemma 5.6.3

En una cola M/M/1 tal que ρ < 1, se tiene que en estado estacionario

i) el número de entidades en el sistema en un instante es independiente de la secuencia de

tiempos de salida pasados;

ii) el tiempo que una entidad pasa en el sistema (espera más servicio) es independiente del
proceso de salida de entidades hasta antes del instante de su propia salida.

Demostración. Argumentamos por reversibilidad. En el proceso hacia adelante en el tiempo,

dado que las llegadas son Poisson, el número de entidades en el sistema en cualquier instante de

179
tiempo es independiente del proceso de llegadas en el futuro. Esto quiere decir que en el proceso
reverso, el número de entidades en el sistema es independiente del proceso de salidas pasadas.
Sin embargo, dado que el sistema es reversible, lo mismo se puede concluir del sistema hacia
adelante en el tiempo, lo que corresponde a i).

Respecto a ii), notamos que el tiempo que una entidad pasa en el sistema es independiente del
proceso de llegada de entidades después de la llegada de dicha entidad (aquí estamos asumiendo
la política FIFO de atención). Visto desde la perspectiva del proceso reverso, vemos que el tiempo
que una entidad pasa en el sistema es independiente de las salidas hasta antes del instante de su
propia salida. Sin embargo, dado que el sistema es reversible, concluimos que lo mismo se cumple
en estado estacionario para el sistema hacia adelante en el tiempo, lo que corresponde a ii). ■

Claramente este resultado se puede extender al caso de k colas M/M/1 en tandem. En dicho caso,
tendremos que denotando con π(n1 , . . . , nk ) la probabilidad estacionaria del estado (n1 , . . . , nk )
donde nj denota el número de entidades en la estación j, tenemos que, bajo la condición que
ρj < 1 para todo j = 1, . . . , k (donde ρj = λ/µj ),

k
n
Y
π(n1 , . . . , nk ) = ρj j (1 − ρj ).
j=1

Adicionalmente, vemos que los argumentos usados en las demostraciones arriba se mantienen
para el caso donde el servidor i cuenta con ci servidores, transformando dicha estación en una
cola M/M/ci . En dicho caso, tenemos que

k
Y
π(n1 , . . . , nk ) = πj (nj ), (7.2)
j=1

donde πj corresponde a las probabilidades estacionarias de una cola M/M/cj con llegada Poisson
de tasa λ y atenciones exponenciales de tasa µj .

Observación 7.2. Importante

El desarrollo anterior también se mantiene válido en el caso donde el ruteo de las entidades a
través de las estaciones es probabilista (piensen en la suma y división de procesos de Poisson).
En tal caso debemos tener en cuenta que la tasa de llegada puede variar de estación a estación
y no podemos permitir feedback.

7.4. Redes de Colas

Consideremos un sistema con k estaciones: las llegadas a la estación i desde el exterior forman
un proceso de Poisson con tasa λi ; esta estación cuenta con ci servidores, cada uno de los cuales
demora un tiempo aleatorio de distribución exponencial de tasa µi en atender a una entidad;
una vez atendida, una entidad se dirige a la estación j con probabilidad Pi,j , independiente de
todo lo demás.

180
Viendo el sistema de estaciones como un grafo dirigido G (donde los nodos son las estaciones y
existe un arco entre i y j si Pi,j > 0) tenemos que los argumentos presentados hasta ahora se
mantienen válidos mientras se cumpla que i) Pi,i = 0 para todo i; y ii) que G no contenga ciclos.
En este caso, tendremos que P es una matriz estrictamente triangular superior.

Para j ≤ k definimos λ¯j como la tasa efectiva de llegada a la estación j. Tenemos que el conjunto
de tasas efectivas (o throughput) son la única solución al sistema

X
λ̄j = λj + Pi,j λ̄i , j ≤ k.
i

Ejemplo 7.6. Calculo tasas efectivas

Calculemos las tasas efectivas a la siguiente red (ver abajo), donde las entidades llegan a la
red a tasas γ, β, y α. Con esto, tenemos que

λ̄1 = γ
λ̄2 = γp + β
λ̄3 = (1 − p)γ
λ̄4 = (1 − p)qγ
λ̄5 = (1 − p)(1 − q)γ + α

2
p

γ 1 4
q
1−p

1−q

181
 Observación 7.3. Importante

En general, tendremos que existe un vector de probabilidades estacionarias cuando se cumple

que λ¯j < cj µj para todo j ≤ k. En tal caso, los resultados anteriores se mantienen, de forma
que el vector de probabilidades estacionarias sigue estando dado por (7.2), salvo que en este
caso, πj corresponde al vector de probabilidades estacionarias de una cola M/M/cj donde
la tasa de atención es µj y las llegadas siguen un proceso de Poisson de tasa λ̄j , para todo
j ≤ k.

¿Qué ocurre si las entidades procesadas pueden volver a servidores? Por ejemplo, consideremos
el siguiente sistema con una sola estación, que cuenta con un único servidor.

p
γ −→ S1

1−p

Si bien el proceso de llegadas externas es un proceso de Poisson, el proceso total no será Poisson.
Para ver esto supongamos que la tasa γ es muy chica en relación a la tasa de atención µ (i.e.
γ/µ´1), y que p = 0,01: cuando llega un cliente hay una posibilidad muy grande de que haya otro
arribo en un intervalo de tiempo corto (el mismo cliente que tiene que atenderse nuevamente),
siendo que en un intervalo cualquiera el tiempo entre llegadas debiese ser grande (debido a que
γ es pequeño), esto viola la propiedad de incrementos independientes.

Supongamos ahora que la matriz de ruteo P no es estrictamente triangular superior. Aún pode-
mos representar el sistema como una cadena de Markov en tiempo continuo, donde el estado es
un vector n = (n1 , . . . , nk ) donde nj representa el número de entidades en la estación j, j ≤ k.

Como vimos anteriormente, los procesos de llegada a las estaciones no son necesariamente Pois-
son, por lo que el sistema i no es necesariamente una fila M/M/ci , lo que dificulta el cálculo de
las probabilidades marginales de ni . Más importante, es posible mostrar que la cadena de Markov
asociada al sistema no es reversible, lo que impide utilizar los argumentos que usamos para el
caso de colas en tandem. Sin embargo, del contenido de reversibilidad, sabemos que cuando una
cadena no es reversible, podemos tratar de adivinar un vector π junto a una matriz Q∗ , de forma
que la cadena reversa esté definida por Q∗ y las probabilidades estacionarias estén dadas por π.
Recordamos aquel resultado.

182
 Proposición 7.1. Caracterización probabilidades estacionarias

Consideremos una cadena de Markov caracterizada por Q. Si existe un vector de probabilidad

π, y una matriz Q∗ tal que
∗
πi qi,j = πj qj,i , i, j ∈ N,

y
X X
∗
qij = qij , i ∈ N,
j̸=i j̸=i

entonces π es el vector de probabilidades estacionarias y Q∗ caracteriza a la cadena reversa.

Utilizaremos este resultado para calcular el vector de probabilidades estacionarias π. Para esto
debemos conjeturar π y el proceso reverso (definido por Q∗ ).

Conjetura para π. Nos pondremos en un caso muy optimista: supongamos que, si bien los pro-
cesos de llegada a las estaciones no son Poisson, las probabilidades marginales de ni corresponde
a aquella de un sistema M/M/ci , para cada estación i ≤ k; adicionalmente, como en el caso de
las colas en tandem, supongamos que las componentes de n son independientes, con eso tenemos
que un candidato a vector π está dado por

k
Y
π(n1 , . . . , nk ) = πj (nj ),
j=1

donde πj corresponde a las probabilidades estacionarias de una cola M/M/cj con llegada Poisson
de tasa λ̄j y atenciones exponenciales de tasa µj , donde {λ̄i , i ≤ k} corresponde a la solución del
sistema lineal.
X
λ̄j = λj + Pi,j λ̄i , j ≤ k.
i

(Suponemos también que λ̄i < ci µi , para que exista estado estacionario.)

Conjetura para Q∗ . Conjeturamos que el proceso reverso es también un sistema de colas, de

forma que no caracterizamos Q∗ directamente, sino que a través de los elementos que definen
una red de colas. Entonces, para caracterizar dicho proceso necesitamos encontrar una matriz de
ruteo P ∗ y un conjunto de tasas de llegadas exteriores a cada estación {λ∗i : i ≤ k}.

Pensando en el proceso reverso, la tasa a la cual entidades pasan, en el largo plazo, desde la
estación i a la j debe coincidir con aquella con que las entidades pasan de la estación j a la i
en el proceso hacia adelante en el tiempo. Notando que tanto en el proceso hacia adelante en el
tiempo como en el reverso, la tasa de salida desde la estación i es λ̄i , i ≤ k, al igualar las tasas,
concluimos que P ∗ debe ser tal que
∗ λ̄j
Pi,j = Pj,i .
λ̄i

183
Por otro lado, salidas al exterior desde la estación i en el proceso adelante en el tiempo corres-
ponden a llegadas desde el exterior en el sistema reverso. Concluimos entonces que
 
X
λ∗i = λ̄i 1 − Pi,j  , i ≤ k.
j

Con estas dos conjeturas (respecto a π y Q∗ ) debemos corroborar que las condiciones en el
resultado de arriba se cumplen. Para esto, consideremos un par de estados n y n′ , y chequeamos
que la condición
π(n)qn,n′ = π(n′ )qn∗ ′ ,n

se cumple. Para simplificar el análisis, supondremos que ci = 1 para todo i, entendiendo que el
análisis se mantiene para el caso más general.

Caso I: n′ = (n1 , . . . , ni + 1, . . . , nk ). Notamos que la transición corresponde a una llegada desde

el exterior a la estación i para la cadena hacia adelante en el tiempo y una salida al exterior
desde la estación i para la cadena reversa. Por lo tanto, tenemos que
X
qn,n′ = λi , qn∗ ′ ,n = µi (1 − ∗
Pi,j ).
j

Notando que π(n′ ) = π(n)ρi , tenemos que

π(n) qn,n′ = π(n) λi

µi
= π(n′ ) λi
λ̄i
′ µi
X
= π(n ) (λ̄i − Pj,i λ̄j )
λ̄i j
X λ̄j
= π(n′ ) µi (1 − Pj,i )
j
λ̄i
X
= π(n′ ) µi (1 − ∗
Pi,j )
j
′
= π(n ) qn∗ ′ ,n .

Caso II: n′ = (n1 , . . . , ni + 1, . . . , nj − 1, . . . , nk ). Notamos que la transición corresponde a una

entidad que completa su atención en la estación j (i) y se mueve a la estación i (j), en la cadena
hacia adelante (reversa). Por lo tanto, tenemos que

qn,n′ = µj Pj,i , qn∗ ′ ,n = µi Pi,j

∗
.

Notando que π(n′ ) = π(n)ρi /ρj , tenemos que

π(n) qn,n′ = π(n) µj Pj,i

λ¯j µi
= π(n′ ) µj Pj,i
λ̄i µj
= π(n′ ) µi Pi,j
∗

= π(n′ ) qn∗ ′ ,n .

184
Caso III: n′ = (n1 , . . . , ni − 1, . . . , nk ). Notamos que la transición corresponde a una salida al
exterior a la estación i para la cadena hacia adelante en el tiempo y una llegada desde el exterior
a la estación i para la cadena reversa. Por lo tanto, tenemos que
X X
qn,n′ = µi (1 − Pi,j ), qn∗ ′ ,n = λ̄i (1 − Pi,j ).
j j

Notando que π(n) = π(n′ )ρi , tenemos que

X
π(n) qn,n′ = π(n) µi (1 − Pi,j )
j
λ̄i X
= π(n′ ) µi (1 − Pi,j )
µi
j
X
′
= π(n ) λ̄i (1 − Pi,j )
j
′
= π(n ) qn∗ ′ ,n .

Hemos probado lo siguiente

Proposición 7.2. Probabilidades estacionarias red de colas

En la red de colas con matriz de ruteo P arbitraria, si λ̄i < ci µi , para todo i ≤ k, tenemos
que el vector de probabilidades estacionarias está dado por
k
Y
π(n1 , . . . , nk ) = πj (nj ),
j=1

donde πj corresponde a las probabilidades estacionarias de una cola M/M/cj con llegada
Poisson de tasa λ̄j y atenciones exponenciales de tasa µj , donde {λi , i ≤ k} corresponde a la
solución del sistema lineal.
X
λ̄j = λj + Pi,j λ̄i , j ≤ k.
i

Adicionalmente, en estado estacionario: i) las salidas hacia el exterior desde la estación i

forman un proceso de Poisson de tasa λ̄i (1 − j Pi,j ); y ii) el número de entidades en las
P

distintas estaciones son variables aleatorias independientes.

185
7.5. Ejercicios resueltos
Pregunta 7.1. Examen - Primavera 2018

Los k profesores auxiliares de un curso buscan contratar a alguien que se disfrace de Santa
durante las fiestas. Para esto consideran el siguiente proceso: Candidatos llegan al lugar de
las entrevistas de acuerdo a un proceso de Poisson de tasa λ [candidatos/hora] y se colocan en
fila para ser entrevistados por el profesor auxiliar 1. En general, el profesor auxiliar i demora
un tiempo aleatorio de distribución exponencial de tasa µi = µ/i [1/horas] en entrevistar a
alguien, y dicha entrevista es exitosa con probabilidad pi = i/(i + 1). Cuando un candidato
fracasa tras una entrevista, es despachado a su casa. Por otro lado, un candidato que con-
cluye exitosamente su entrevista con el profesor auxiliar i procede a esperar su turno para
entrevistarse con el profesor auxiliar i + 1, excepto en el caso que la entrevista haya sido con
el último profesor auxiliar (en cuyo caso los candidatos también se retiran, pero sabiendo que
potencialmente serán contratados). Boris quiere entrevistarse para el puesto, pero va muy
atrasado, por lo cual el proceso ya lleva un largo tiempo operando cuando llega.

1. Modele el sistema de entrevistas como una red de colas. Indique las condiciones sobre
los parámetros del problema para que exista estado estacionario.

2. Boris quiere saber cuánto tiempo debería presupuestar (en valor esperado) para las
entrevistas, pensando en que está seguro de triunfar en todas ellas.

3. Suponga que se cumplen las condiciones de estado estacionario. Al llegar al sistema,

Boris nota que hay muchas personas esperando su turno para entrevistarse con el primer
profesor auxiliar. ¿Cuál es la probabilidad que todos los otros profesores auxiliares se
encuentren desocupados en ese momento?

4. Suponga ahora que, aprovechando que nadie lleva registro de la identidad de los candida-
tos, una vez fracasada una entrevista, los candidatos se mezclan con la gente esperando
su entrevista con el profesor auxiliar 1 (es decir, simulan ser nuevos candidatos). Modele
este nuevo sistema como una red de colas e indique las condiciones para alcanzar estado
estacionario. En valor esperado, ¿cuánto tiempo estará Boris en el sistema, pensando
en que él está seguro de triunfar en todas las entrevistas (al primer intento)?

Solución parte 1. El sistema esta formado por k colas M/M/1 en serie. La cola i corresponde
a las entrevistas realizadas por el auxiliar i, tiene una tasa de atención µi = µ/i efectiva de
llegada
i−1
Y
λi = λ pj = λ/i.
j=1

Definimos ρi := λi /µi = λ/µ = ρ. La condición de estacionario es entonces ρ < 1.

Solución parte 2. El tiempo que Boris debería presupuestar es la suma de los tiempos esperados

186
de estadía (de largo plazo) en k colas M/M/1, cada una con parámetros λ/i y µ/i. Esto es
k
X i k(k + 1)
WB = = .
µ−λ 2(µ − λ)
i=1

Solución parte 3. Sabemos que, por reversibilidad, el número de personas en las colas son
variables aleatorias independientes. Por lo tanto el hecho que haya gente esperando en la primera
cola no perturba las probabilidades estacionarias en el resto de las colas. Con esto, la probabilidad
P buscada es
P = (1 − ρ)k−1 .

Solución parte 4. El sistema sigue siendo k colas, pero ahora hay una nueva matriz de ruteo. En
terminos prácticos, tenemos que recalcular las tasas efectivas de llegadas. Estas son la solución
al sistema

X 1
λ1 = λ + λj
j+1
j≥1
i
λi+1 = λi i≥1
i+1

Resolviendo tenemos que

λ
λ1 = P 1
1− j≥1 j(j+1)
1
λi = λ1 i>1
i

La condición de estado estacionario ahora es λ1 < µ, y el tiempo esperado para Boris ahora
cambia a WB = µ−λ1 .
k

Pregunta 7.2. Examen - Otoño 2019

De Lunes a Miércoles, pacientes llegan a un laboratorio de acuerdo a un proceso de Poisson

de tasa λ [pacientes/hora] para realizarse una secuencia de hasta n exámenes, indexados por
i = 1, . . . , n. Todos los pacientes comienzan realizándose el examen 1. Cada paciente demora
un tiempo aleatorio exponencial de tasa µ [1/hora] en realizarse el examen i, el que requiere
la supervisión del único técnico especialista que hay en el laboratorio para ese examen, por
lo que los pacientes esperan su turno en orden de llegada. Una vez concluido el examen i, los
pacientes se retiran con probabilidad p, y con probabilidad (1 − p) deben realizarse el examen
i + 1, para i < n. Todos los pacientes que se realizan el examen n se retiran del laboratorio.

1. Modele el sistema de atención del laboratorio como una red de colas. Encuentre las
condiciones para que exista un estado estacionario.

187
 De Jueves a Sábado, pacientes vuelven al laboratorio de acuerdo a un proceso de Poisson
de tasa λ [pacientes/hora], a buscar los resultados de sus exámenes, los que son entregados
por los técnicos especialistas. Cada ténico demora un tiempo aleatorio exponencial de tasa
µ [1/hora] en entregar el resultado a un paciente, independiente de todo. Cada paciente
comienza recolectando el resultado del último examen que se tomo, y comienza a volver a
través de la secuencia de exámenes que se tomo, hasta terminar recolectando el resultado del
examen 1, tras lo cual se retira del laboratorio.

2. Cuál es la probabilidad de que un paciente cualquiera comience a recolectar los resul-

tados de sus exámenes partiendo por el examen i?

3. Modele el sistema de atención del laboratorio como una red de colas. Encuentre las
condiciones para que exista un estado estacionario.

4. Compare los tiempos promedio de estadía en el laboratorio durante los días de la se-
mana.

Solución parte 1. La red de colas cuenta con n estaciones, una por cada examen. Solo existen
llegadas externas a la estación 1 (tasa λ). La estación i corresponde a una M/M/1, con tasa
de atención es µ, y su tasa efectiva de llegada es λ(1 − p)i−1 . La matriz de ruteo es tal que
Pi,i+1 = (1 − p), para i < n.

Con esto, la condición de estado estacionario es λ < µ.

Solución parte 2. Es la probabilidad que el ultimo examen que tuvieron fue el i. Eso es
P = (1 − p)i−1 p (distribuye geométrica).

Solución parte 3. La red de colas cuenta con n estaciones, una por cada examen. La tasa
externa de llegada a la estación i es λ(1 − p)i−1 p para i < n, y λ(1 − p)n−1 para i = n. La
estación i corresponde a una M/M/1, con tasa de atención es µ, y su tasa efectiva de llegada es
λ(1 − p)i−1 . La matriz de ruteo es tal que Pi+1,i = 1, para i < n.

Con esto, la condición de estado estacionario es λ < µ.

Solución parte 4. Las tasas efectivas de llegada a cada estación son las mismas en cada situa-
ción, por lo que el número esperado de pacientes en el largo plazo en cada estación, y por lo
tanto en el sistema, es el mismo. Utilizando Little en ambas situaciones concluimos que el tiempo
esperado de estadía también es el mismo.

Pregunta 7.3. Examen Recuperativo - Primavera 2018

Considere las visitas al nuevo sitio web que ha lanzado Boris, en el cual da consejos para
enfrentar entrevistas de trabajo. El mapa del sitio tiene una estructura de árbol, donde la
raíz representa la página de inicio del sitio (por lo tanto todas las páginas - salvo la raíz -

188
 tienen una página madre y potencialmente múltiples páginas hijas - salvo las páginas hoja).

Visitantes al sitio web llegan a la raíz del sitio de acuerdo a un proceso de Poisson de tasa
λ. Cada vez que alguien llega a una página del sitio web, permanece en ella por un tiempo
exponencial de tasa µ (independiente de si la ha visitado en el pasado o no), tras lo cual
puede volver a la página madre, lo que ocurre con probabilidad p, o visitar una página hija
(escogida al azar), lo que ocurre con probabilidad 1 − p. En este contexto, visitar la madre
del nodo raíz representa abandonar el sitio, al igual que lo es visitar hijas de páginas hoja.

1. Modele el número de visitantes al sitio web (en todas sus páginas) como una red de
colas. ¿Qué condiciones son necesarias para que exista estado estacionario? Entrege una
expresión para las tasas efectivas de llegada a cada componente de dicha red.

2. Calcule las probabilidades estacionarias del sistema. ¿Cuánto tiempo pasa en promedio
un visitante navegando por el sitio web?

3. Verdadero o falso: si el sitio web de Boris tiene una capacidad para C visitantes simul-
táneos, podemos fácilmente calcular las probabilidades estacionarias de dicho sistema
simplemente escalando aquellas encontradas en la parte 2. Justifique su respuesta.

Solución parte 1. Cada página del árbol es una cola. Cada cola tiene capacidad infinita.
Definamos N como el conjunto de páginas y para i ∈ N definamos M (i) como la página madre
de la página i, H(i) el conjunto de hijas de la página i (esta página y conjunto son vacíos en el
caso de la página raíz y páginas hojas, respectivamente). La matriz de ruteo P es

p j = M (i)
Pi,j =
(1 − p)/|H(i)| j ∈ H(i).

Dado que cada cola tiene capacidad infinita, no existen condiciones para alcanzar estado esta-
cionario. Las tasas efectivas de llegada son la solución al siguiente sistema.

X 1−p
λi = λ 1{i es la pagina madre} + p λj + λ , ∀ i ∈ N.
|H(M (i))| M (i)
j∈H(i)

Solución parte 2. Considerando la cadena de Markov subyacente, donde el estado n = (ni , i ∈

N ), el vector de probabilidades estacionarias es
Y ρni
πn = i
e−ρi ,
ni !
i∈N

donde ρi = λi /µ. Utilizando el hecho que la marginal del número de personas en la página i es
Poisson(ρi ), y que la esperanza de una Poisson es su parámetro, tenemos que

L 1X
W = = ρi .
λ λ
i∈N

189
Solución parte 3. Falso. La afirmación seria cierta si la cadena subyacente fuese reversible. En
este caso la cadena no lo es (por ejemplo, en el proceso reverso personas llegan desde fuera del
sistema a las paginas hoja, lo que no ocurre en el proceso original).

Pregunta 7.4. Control 5 - Primavera 2018

Un club de fútbol se apresta a escoger al Entrenador. para su equipo. Para esto, los k direc-
tores entrevistan a los numerosos postulantes, quienes llegan a la sala donde se realizan las
entrevistas de acuerdo a un proceso de Poisson de tasa λ. Al llegar a dicha sala, los candida-
tos escogen al azar a uno de los directores y proceden a esperar su turno para entrevistarse
con el director. El director i por su parte demora en entrevistar a un candidato un tiempo
aleatorio distribuido exponencial de tasa µi , para i ≤ k. Tras entrevistarse con un director,
los candidatos se retiran.

1. Considerando que la sala de entrevistas solo tiene capacidad para C personas (excluyen-
do a los directores), modele el estado de ocupación de los directores como una cadena
de Markov en tiempo continuo, entregue condiciones para la existencia de estado esta-
cionario y calcule (en forma cerrada) las probabilidades estacionarias asociadas.

2. Suponga ahora que las entrevistas se realizarán en el estadio del club (y por lo tanto
podemos considerar la capacidad infinita para cualquier fin práctico), pero que, sin
embargo, al terminar la entrevista con uno de los directores, se le pide a un candidato
que se entreviste nuevamente con otro director con probabilidad p (independiente de
con quién y cuántas veces se ha entrevistado en el pasado, por lo que es posible que un
candidado se entreviste dos o más veces con un mismo director, pero nunca de forma
consecutiva).

Modele el sistema de atención como una red de colas, determine las condiciones pa-
ra la existencia de probabilidades estacionarias y calcule el vector de probabilidades
estacionarias.

3. ¿Cuánto tiempo espera en promedio un candidato hasta entrevistarse por primera vez?
¿Cuántas entrevistas tiene en promedio un candidato? ¿Cuánto tiempo en promedio
pasa en total un candidado en el sistema hasta abandonarlo?

4. ¿Cuánto tiempo pasa en promedio en el sistema un candidato, de quien se sabe que

solamente se entrevistó con dos o menos directores distintos?

Solución parte 1. Consideremos el sistema descrito en el enunciado, pero sin restricción de

capacidad. Por lo tanto, se tiene k filas M/M/1, cada una con tasa de llegada λ
k y su respectiva
tasa de servicio µi . El vector s = (s1 , . . . , sk ) ∈ S = Nk0 con la cantidad de personas en cada una
de las k filas es una cadena reversible, ya que cada si lo es. Las probabilidades estacionarias de
esta cadena son
k 
λ si
  
Y λ
πs = 1− .
kµi kµi
i=1

190
 Pk
Podemos truncar esta cadena al conjunto A = {s ∈ S : i=1 si ≤ C}, resultando el sistema
deseado, con probabilidades estacionarias
Qk   s i 
λλ
i=1 1 − kµi
kµi
πsA = P Qk  λ ai  .
λ
a∈A i=1 kµi 1 − kµi

Finalmente, podemos ver que no existen condiciones de estado estacionario.

p
Solución parte 2. Cada servidor i posee una tasa efectiva de llegadas λi = λ
j̸=i k−1 λj .
P
k +
Estas tasas son todas iguales (λi = λj ∀ i, j), por lo cual se puede despejar y obtener λ
λi = k(1−p)
para todo i. Luego, como condición de estabilidad, se debe cumplir que λ
k(1−p) < µi para todo i.
Las probabilidades estacionarias de este sistema entonces son
k  si  
Y λ λ
πs = 1− .
k(1 − p)µi k(1 − p)µi
i=1

Solución parte 3. Sea WiQ el tiempo promedio de espera de un candidato si llega a hacer
fila para entrevistarse con el director i. Este valor es el mismo que se obtendría para una fila
M/M/1:
λi
WiQ = .
µi (µi − λi )
Desconociendo el director al que llega un candidato cualquiera, esta esperanza viene dada
por
k k
1 X λi 1
WiQ ·
X
WQ = = · .
k µi (µi − λi ) k
i=1 i=1

El número de entrevistas por candidato puede ser visto como una variable aleatoria con distri-
bución geométrica de parámetro 1 − p. Por lo tanto, su esperanza simplemente es 1−p .
1

Para calcular el tiempo esperado total en el sistema, podemos usar la ley de Little. Para esto,
definimos Li como el largo promedio en largo plazo de personas en la cola i y recordamos desde
las formulas de la cola M/M/1 que
λi
Li = .
µi − λi
Dado que L = i Li , tenemos que
P

k k
1 1 X λi 1 X 1 1
W = L= = · .
λ λ µi − λ i (1 − p) µi − λi k
i=1 i=1

Solución parte 4. Consideremos momentaneamente un sub-sistema compuesto por 2 de los k

directores, digamos i y j. Usando el resultado de la parte anterior, tenemos que un candidato
pasa en promedio en este sub-sistema (en el largo plazo) un tiempo
 
1 1 1
Wi,j = + .
2(1 − p) µi − λi µj − λj

191
Ahora pensamos en Wi,j como el tiempo que pasa un candidato en el sistema, condicional en que
era posible visitar solo a los directores i y j. Obtenemos el resultado descondicionando sobre i y
j, notando que cualquier par de directores es equiprobable. Esto es,
X Wi,j
W̃ = .
k(k − 1)
{(i,j) : i̸=j}

Pregunta 7.5. 6.11 (Problema 1, Control 3, Otoño 2018)

Considere la asistencia del publico a un partido de fútbol profesional Chileno. Los hinchas
llegan a la entrada del estadio según un proceso de Poisson de tasa λ. En la entrada, un
único guardia se realiza el control de identidad a cada asistente. Esto demora un tiempo
exponencialmente distribuido de media 1/µ1 (i.i.d.). Un asistente que pasa el control de
identidad, con probabilidad p se dirige directamente a su asiento, y con probabilidad (1 − p)
primero pasa a comprar un snack. El puesto de snacks es atendido por su dueño, quien atiende
a un cliente a la vez, demorando un tiempo aleatorio exponencial de tasa µ2 . Tras comprar
su snack, los asistentes se dirigen a sus asientos.

El partido dura lo que parece ser una eternidad. Cada asistente, independiente del resto, se
aburre y decide retirarse tras un tiempo aleatorio exponencial de tasa µ3 (contabilizado desde
el instante en que llegan a su asiento). Al retirarse del recinto, una fracción r de los asistentes
pasan por la tienda de souvenires ubicada al interior del estadio, la cual es atendida por un
único empleado, quien demora un tiempo aleatorio exponencial de tasa µ4 en atender a un
cliente (el resto de los asistentes se retira directamente sus casas). Una vez comprado un
souvenir, un asistente retorna con probabilidad q a su asiento (el resto se retira a sus casas).

1. Modele la situación descrita como una red de colas. Bajo que condiciones existe un
estado estacionario?

2. Que fracción del tiempo (en el largo plazo) pasa desocupado el dueño del puesto de
snacks?

3. Cuál es la probabilidad que hayan k personas viendo el partido (en el largo plazo)?

4. Cuanto pasa en promedio (en el largo plazo) un asistente en el estadio?

5. Cuanto pasa en promedio (en el largo plazo) un asistente en el estadio que no compra
souveniers?

6. En el entretiempo un carabinero llega supervisar la labor del guardia (en la entrada

al estadio). El carabinero se retira tras supervisar n controles de identidad. Calcule la
probabilidad que el carabinero este supervisando al guardia durante más de t unidades
de tiempo.

Solución parte 1. La representación gráfica del problema es:

192
Para analizar las condiciones en las que existe el estado estacionario, se plantean las siguiente
ecuaciones:

(1) λ1 = λ
(2) λ2 = λ1 · (1 − p)
(3) λ3 = λ1 · p + λ2 + λ4 · q
(4) λ4 = λ3 · r

Reemplazando (1) en (2), se obtiene:

(5) λ2 = λ · (1 − p)

Ahora, reemplazando (1), (4) y (5) en (3), se obtiene:

λ3 = λ · p + λ · (1 − p) + λ3 · r · q

Obteniendo:

λ1 = λ
λ2 = λ · (1 − p)
λ
λ3 =
1−q·r
λ·r
λ4 =
1−q·r

Imponiendo condiciones de estabilidad, se tiene:

193
 λ1 < µ1 ⇒ λ < µ1
µ2
λ2 < µ2 ⇒ λ<
(1 − p)
µ4 · (1 − q · r)
λ4 < µ4 ⇒ λ<
r
Notemos que no se agrega la ecuación asociada al λ3 ya que al ser un sistema del tipo M/M/∞
tiene infinitos servidores (un servidor para cada entidad), por ende el proceso siempre alcanzara
estado estacionario.

Luego,
µ2 µ4 · (1 − q · r)
λ∗ = min{µ1 , , }
(1 − p) r

Solución parte 2. Notemos que el número de entidades del sistema M/M/1 se puede modelar
como una cadena de Markov de tiempo continuo, más específicamente como un proceso de
nacimiento y muerte. Así, como se vio en clases para un proceso de nacimiento y muerte de
parámetros (λ, µ), se tiene que:
λ
p0 = 1 − =1−ρ
µ
Y en general
pk = (1 − ρ) · ρk

es decir tiene una distribución geométrica. Como se pide la fracción de tiempo al largo plazo
donde el número de entidades en el sistema de la tienda de snack es cero, la solución es:
λ2 λ · (1 − p)
p0 = 1 − ρ = 1 − =1−
µ2 µ2

Solución parte 3. Se debe identificar que estamos hablando de un proceso del tipo M/M/∞.
Las probabilidades estacionarias vienen dadas por

λk −λ
pk = k
·e µ , ∀n = 0, 1, 2, ...
µ · k!

Entonces, la probabilidad que hayan k personas en el estadio (asiento) es:

λ
( 1−q·r )k λ
− 1−q·r

pk = ·e µ3
.
(µ3 )k · k!
Solución parte 4. Notemos que un asistente se encuentra en el estadio desde el momento que
entra al sistema, así, para encontrar e tiempo promedio que pasa un asistente en el estadio de-
bemos considerar los 4 sistemas.

Una de las relaciones de teoría de colas que se basa en Conservación en estado estacionario es
la fórmula de Little, donde sabemos
L=λ·W (7.3)

194
donde λ es la tasa promedio de llegada de las entidades al sistema, L el número promedio de
entidades en el sistema y W es el tiempo promedio de permanencia de una entidad en el sistema
en estado estacionario.

Así, como sabemos que la tasa promedio de llegada de los asistentes es λ, para poder calcular
W debemos despejarlo de (1)
L
W = (7.4)
λ
Así, sólo nos falta calcular L, que se calcula como sigue

L = L1 + L2 + L3 + L4

Donde

ρ1 λ1 λ
L1 = LM/M/1 = , con ρ1 =
=
1 − ρ1 µ1 µ1
ρ2 λ2 λ · (1 − p)
L2 = LM/M/1 = ,
con ρ2 = =
1 − ρ2 µ2 µ2
λ3 λ
L3 = LM/M/∞ = ρ3 , con ρ3 = =
µ3 (1 − q · r) · µ3
ρ4 λ4 λ·r
L4 = LM/M/1 = , con ρ4 = =
1 − ρ4 µ4 (1 − q · r) · µ4

Por lo tanto,
 
λ λ · (1 − p) λ λ·r
W =λ· + + +
µ1 µ2 (1 − q · r) · µ3 (1 − q · r) · µ4

Solución parte 5. Del grafo asociado a la red de colas, vemos que alguien que no pasa por
la tienda de souvenires pasa por la entrada, por el partido (asiento) y con probabilidad (1 − p)
por la tienda de snacks. Por lo tanto, tenemos que su tiempo de estadía en el sistema esta dado
por

Wno souvenirs = W1 + (1 − p) · W2 + W3
= L1 /λ + (1 − p) · L2 /(λ · (1 − p)) + 1/µ3
1 1−p 1
= + + .
µ1 − λ µ2 − (1 − p) · λ µ3

Solución parte 6. En estado estacionario, la salida de la estación “Entrada” es un proceso de

Poisson de tasa λ. Por lo tanto, denotando con X una variable aleatoria distribuida Poisson(λ·t),
tenemos que la probabilidad P que el carabinero este supervisando al guardia más de t unidades
de tiempo esta dada por

P = P[X < n]
n−1
X (λ · t)k e−λ·t
= .
k!
k=1

195
 Pregunta 7.6. Control 3 - Otoño 2019

Los auxiliares del curso realizarán un horario de consulta para ayudar a resolver la tarea 3.
Los alumnos del curso (quienes para fines de esta pregunta son infinitos) llegan al horario de
consulta de acuerdo a un proceso de Poisson de tasa λ [alumnos/minuto]. Los alumnos son
recibidos por Sebastián, quien demora un tiempo aleatorio exponencial de tasa µ1 [1/minutos]
en determinar el tipo de asistencia requerida y derivar al alumno al auxiliar(es) encargado(s)
de entregar la asistencia pertinente.

De experiencias anteriores, se sabe que una fracción p de las consultas se refieren a aclaraciones
de enunciado, mientras que una fracción (1 − p) se refiere a programación en Julia. Las
consultas relativas al enunciado son resueltas por Natalia y Simón: cada uno de ellos atiende
un alumno a la vez, y demoran un tiempo exponencial de tasa µ2 [1/minutos] en resolver una
consulta. Por su parte, las dudas relativas a Julia son resueltas por Pablo, quien demora un
tiempo aleatorio exponencial de tasa µ3 [1/minutos] en resolver una consulta.

Tras la resolución de una consulta de enunciado (Julia), pueden ocurrir 3 cosas: i) una duda
relativa Julia (enunciado) surge con probabilidad r (independiente de todo lo demás); ii) otra
duda surge con probabilidad q, pero no es claro su ámbito, por lo que el alumno vuelve a
consultar a Sebastián; o iii) no existen mas dudas, con lo que el alumno abandona el horario
de consulta. (q + r < 1)

De la misma forma, tras la resolución de una consulta de programación, pueden ocurrir 3

cosas: i) una duda relativa al enunciado surge con probabilidad r; ii) otra duda cuyo ámbito
se desconoce surge con probabilidad q ; o iii) el alumno abandona el horario de consulta.

1. Modele el horario de consulta como una red de colas, y determine las condiciones para
la existencia de estado estacionario.

2. Cuál es la probabilidad que, en el largo plazo, hayan i alumnos resolviendo (o esperando

resolver) consultas con Natalia y Simón? (Hint: escriba el resultado en función de ρ =
2 µ2 , donde λ̄2 denota la tasa efectiva de llegada de consultas de enunciado).
λ̄2

3. Cuánto tiempo pasan en promedio (en el largo plazo) los alumnos que no tuvieron dudas
de enunciado en el horario de consulta? (Hint: muestre que el número de consultas de
programación de este tipo de alumno tiene distribución geométrica.)

4. Al cabo de mucho tiempo, Pablo, Natalia y Simón tienen una gran cantidad de alumnos
esperando. Cuál es la probabilidad de que Sebastián se encuentre desocupado en ese
instante?

Solución parte 1. Tenemos 3 estaciones, una M/M/1 (estación 1, Sebastián), una M/M/2
(estación 2, Natalia y Simon), y otra M/M/1 (estación 3, Pablo). Las tasas externas de llegada
son λ1 = λ, λ2 = λ3 = 0. La matriz de ruteo es tal que P1,2 = p, P1,3 = 1 − p, P2,3 = P3,2 = r y
P2,1 = P3,1 = q.

196
Las tasas efectivas de llegada son la solución al siguiente sistema.

λ̄1 = λ + q λ̄2 + q λ̄3

λ̄2 = pλ̄1 + r λ̄3
λ̄3 = (1 − p)λ̄1 + r λ̄2

Con un poco de álgebra, obtenemos que

 
1−r
λ¯1 = λ
1−r−q
 
p + (1 − p) r
λ¯2 = λ
(1 − r − q)(1 + r)
 
1 − p + pr
λ¯3 = λ
(1 − r − q)(1 + r)

Las condiciones de estado estacionario son λ̄1 < µ1 , λ̄2 < 2µ2 y λ̄3 < µ3 .

Solución parte 2. Modelando esta cola como un proceso de nacimiento y muerte, tenemos que
las probabilidades estacionarias estan dadas por

πi = π0 2ρi i ≥ 1.

Despejando el valor de π0 , tenemos que

∞
!−1
X
π0 = 1+ 2ρi
i=1
∞
!−1
X
2 ρi − 1
i=0
 −1
2
−1
1−ρ
 
1−ρ
.
1+ρ

Concluimos que πi = 2ρi 1−ρ

1+ρ , para i ≥ 0.

Solución parte 3. Notamos que el número de veces X que  un alumno

 en cuestión pasa por la
q
estaciónes 1 y 3 se distribuye geométrica con parámetro 1 − 1−r , por lo tanto, la esperanza
del tiempo T que pasa este alumno en horario de consulta es

   −1
L1 L3 q
E{T } = (W1 + W3 ) · E{X} = + · 1− ,
λ̄1 λ̄3 1−r
donde usamos Little para obtener los tiempos en las estaciones 1 y 3 (una pasada) y el hecho
que la esperanza de una variable geométrica (que parte en 1) es el inverso del parámetro.

197
Solución parte 4. Utilizamos el hecho que, en el largo plazo, el número de alumnos en cada
estación son variables aleatorias independientes. Por lo tanto, la probabilidad que Sebastián se
encuentre desocupado en el lago plazo es (desde las formulas de una M/M/1)

λ¯1
π0 = 1 − .
µ1

Pregunta 7.7. Control 3 - Otoño 2019

Una vez concluido el semestre, los (infinitos) alumnos del curso van de paseo a acampar a
un parque nacional que tiene N zonas ubicadas alrededor del lago conectadas por un único
circuito circular. Los alumnos llegan a la única boletería del parque según un proceso de
Poisson de tasa λ [alumnos/minuto], donde un único vendedor tarda un tiempo de distribución
exponencial de media 1/µ0 minutos en atender a cada alumno. Una vez dentro del parque,
cada alumno tarda un tiempo de distribución exponencial de media 1/µ en recorrer la zona
en la que se encuentra, tiempo tras el cual decide pasar a la siguiente zona del circuito con
probabilidad p o abandonar el parque con probabilidad 1 − p (cada zona cuenta con su propia
salida). Todo visitante parte su recorrido en la zona 1, y todo visitante que llega a la zona N
abandona el parque después de recorrer dicha zona.

1. Modele la situación como una red de colas, determine las condiciones para la existencia
de probabilidades estacionarias y calcúlelas.

2. En el largo plazo, cuánto tiempo pasa en promedio un alumno en el parque?

Los Domingos el acceso al parque es liberado, por lo que los visitantes pueden entrar di-
rectamente a cualquiera de zona del parque (sin pasar por boletería). En este escenario, los
alumnos continúan llegando al parque según un proceso de Poisson de tasa λ [alumnos/minu-
to], pero eligen de forma equiprobable que zona recorrer primero. Una vez dentro del parque,
tras recorrer una zona, un alumno decide avanzar a la siguiente zona, retroceder a la zona
anterior o abandonar el parque con igual probabilidad, independiente de las zonas que ha
visitado con anterioridad (para estos efectos, los visitantes en la zona N que deciden avanzar,
lo hacen a la zona 1, y los visitantes en la zona 1 que deciden retroceder, lo hacen a la zona
N ).

3. Modele esta nueva situación como una red de colas, determine las condiciones para la
existencia de probabilidades estacionarias y calcúlelas.

4. En el largo plazo, cuánto tiempo pasa en promedio un alumno en el parque?

Solución parte 1. Tenemos N +1 estaciones (la boletería, más cada zona). La boletería (estación
0) es una M/M/1, mientras que la zona i (estación i) es una M/M/∞. La tasas externas de
llegada son λ0 = λ, y λi = 0 para todo i > 0. La matriz de ruteo es tal que P0,1 = 1, y Pi,i+1 = p,
para todo i ∈ {1, . . . , N − 1}.

198
Las tasas efectivas de llegada a cada estación son

λ¯0 = λ, λ̄i = pi−1 λ, i > 0.

La condición de estado estacionario es λ < µ0 .

El vector de probabilidades estacionarias es: para n = (n0 , n1 ·, nN )

N
Y ρni
π(n) = (1 − ρ0 )ρn0 0 i
e−ρi ,
ni !
i=1

donde ρi = µi ,
λ̄i
con µi = µ para i > 0.

Solución parte 2. Utilizamos Little, y la formulas para el número promedio de gente en el

sistema para una M/M/1 y una M/M/∞. Tenemos que

N
ρ0 X
L= + ρi .
1 − ρ0
i=1

(Se puede desarrollar más usando la expresión para λ̄i , pero esta bien si lo dejan así). El resultado
viene de aplicar Little:
L
W = .
λ

Solución parte 3. Ahora tenemos N estaciones, todas M/M/∞. La tasa externa de llegada a
la zona i es λi = λ/N . La matriz de ruteo es tal que Pi,i+1 = Pi,i−1 = 1/3, donde se entiende
que i + 1 = 0 cuando i = N , y i − 1 = N cuando i = 1.

Las ecuaciones para calcular las tasas efectivas de llegadas son:

λ̄1 = λ/N + 1/3λ̄2 + 1/3λ̄N ,

λ̄i = λ/N + 1/3λ̄i+1 + 1/3λ̄i−1 , i ∈ {2, · · · , N − 1},
λ̄N = λ/N + 1/3λ̄N −1 + 1/3λ̄1 .

Razonando por simetría, tenemos que la solución al sistema es

λ̄i = 3λ/N, ∀i.

El vector de probabilidades estacionarias es: para n = (n0 , n1 ·, nN )

N
Y ρni
π(n) = i
e−ρi ,
ni !
i=1

donde ρi = µi ,
λ̄i
con µi = µ para i > 0.

Solución parte 4. Razonando de la misma forma que en la parte 2, tenemos que

199
 N  
X 3λ 3λ
L= ρi = N = .
Nµ µ
i=1

Con lo que tenemos que W = 3

µ.

(Una forma alternativa de ver esto es pensar que cada alumno visita en promedio 3 zonas -
esperanza de una geométrica de parámetro 1/3; y que el tiempo promedio de visita a cada zona
es 1/µ.)

Pregunta 7.8. Control 3 - Otoño 2021

Pacientes llegan a un centro de vacunación de acuerdo a un Proceso de Poisson con tasa λ.

Supondremos que una fracción pi de los pacientes requiere inocularse con la vacuna i ≤ N .
Un único funcionario recibe a los pacientes que llegan y los registra, lo que le toma un tiempo
aleatorio distribuido exponencial con tasa α. Tras registrarse, una fracción q de los pacientes se
retiran (no les corresponde vacunarse de acuerdo al calendario de vacunación, independiente
de la vacuna que necesitan). El resto de los pacientes se dirigen a una de las N estaciones
de vacunación. La vacuna i es administrada exclusivamente en la estación de i, la cual es
operada por un único enfermero que demora un tiempo aleatorio distribuido exponencial con
tasa µi en vacunar a un paciente, i ≤ N . Tras vacunarse, los pacientes de dirigen a una
sala de observación de capacidad infinita, donde permanecen un tiempo aleatorio distribuido
exponencial con tasa β, tras lo cual se retiran.

a) Modele como una red de colas, indique el tipo de cola de cada estación y encuentre las
tasas efectivas para cada estación. Indique las condiciones para que hayan probabilida-
des estacionarias y encuéntrelas.

b) Indique el número de pacientes promedio en el sistema y el tiempo promedio que espera

un paciente que recibe su vacuna.

Independiente de la vacuna requerida, una fracción r1 de los pacientes llega a inocularse con
una primera dosis, r2 con una segunda, y r3 con una de refuerzo. La política de atención
en cada estación de vacunación es priorizar las inoculación con dosis de refuerzo y luego
con segunda dosis. En la práctica esto se traduce a que cada enfermero atiende a alguien
que requiere segunda dosis solo cuando no hay gente esperando recibir una dosis de refuerzo
(interrumpiendo servicios si es que es necesario); de la misma forma, solo se atiende a alguien
que requiere una primera dosis solo cuando no hay gente esperando recibir una dosis de
refuerzo o segunda dosis.

c) Cuanto tiempo pasa en promedio alguien que recibe su primera dosis?

Solución parte a) Definimos µ0 = α y µN +1 = β. Con esto, tenemos N + 2 colas; la estación

0(recepción), la estación i (vacuna i), i ≤ N , y la estación N + 1 (observación). La cola i es una
M|M|1 con tasa de atención µi , i ∈ {0, . . . , N }, la cola N + 1 es una M|M|∞ con tasa de atención
µN +1 .

200
Caracterizamos la red de colas con el vector de tasas externas de llegadas, y la matriz de ruteo.
Tenemos que



(1 − q)pj i = 0, j ∈ {1, . . . , N }

λ0 = λ, λi = 0, i ∈ {1, . . . , N + 1}, Pi,j = 1 i ∈ {1, . . . , N }, j = N + 1



0 ∼.
La tasa efectiva de llegada a la cola i es



 λ i=0

λ̄i = λ(1 − q)pi i ∈ {1, . . . , N }



λ(1 − q) i = N + 1.
Para que exista estado estacionario es necesario que λ̄i < µi para i ∈ {0, . . . , N }. La probabilidad
estacionaria asociada al estado n = (n0 , . . . , n)N + 1) es
N nN +1
ni ρN +1 −ρN +1
Y
πn = (1 − ρi )ρi e ,
nN +1 !
i=0

donde ρi = λ̄i /µi , i ∈ {0, . . . , N + 1}.

Solución parte b) Utilizando las formulas de las colas M|M|1 y M|M|∞, tenemos que
N
X λ̄i
L= + ρN +1 .
i=0
µi − λ̄i
El tiempo en el sistema de alguien que recibe la vacuna es
N
1 X 1 1
WV = + pi + ,
µ0 − λ µi − λ̄i β
i=1
que es la suma del tiempo en la cola 0, la esperanza de lo que espera en la cola donde se vacuna,
y el tiempo que demora en observación.

Solución parte c) Antes de partir, definimos la función WV (λ) que entrega el tiempo promedio
en el largo plazo en la estacion de vacunación de alguien que se vacuna cuando la tasa externa
de llegada es λ (es decir, la respuesta de la parte b), como función de λ). Esto es,
N
X 1
WV (λ) = pi ,
i=1
µi − λ̄i (λ)
donde se resalta la dependencia en λ de las tasas efectivas.

La observación clave áca es notar que los clientes que buscan segunda dosis o dosis de refuerzo
no se ven afectados por la presencia de gente que busca su primera dosis. Sea W1 el tiempo
promedio en sistema en el largo plazo de alguien que recibe su primera dosis. Tenemos que

WV (λ) = r1 W1 + (r2 + r3 )WV (λ(r2 + r3 )),

con lo que concluimos que

1 1 1
W1 = + (WV (λ) − (r2 + r3 )WV (λ(r2 + r3 ))) +
µ0 − λ r1 β
.

201
 Pregunta 7.9. Examen - Otoño 2024

Clientes llegan a la entrada de un parque de diversiones de acuerdo a un proceso de Poisson

de tasa λ. Allí son atendidos (en orden de llegada) por un empleado que demora un tiempo
aleatorio distribuido exponencial de tasa µ en recibir el pago y colocar una pulsera que permite
el acceso a todos los juegos del parque. Una vez dentro, los clientes escogen al azar entre los
N juegos del parque. En cada juego, los clientes esperan en linea por su turno; la capacidad
de cada juego es de una persona, y la experiencia del juego dura un tiempo aleatorio de
distribución exponencial de tasa γ (igual para todos los juegos). Una vez salen de un juego,
con probabilidad p los clientes escogen al azar el siguiente juego a usar desde los otros n − 1
juegos, y con probabilidad (1 − p) deciden irse del parque.

a) Modele el estado de ocupación del parque de diversiones como una red de colas y plantee
las condiciones para la existencia de estado estacionario.

b) Cuanto tiempo pasa en promedio un cliente dentro del parque (es decir, excluyendo el
tiempo que demora en ingresar al parque).

c) Cuanto tiempo (en valor esperado) dentro del parque para un cliente haciendo cola para
subirse a un juego?

Suponga ahora que una fracción q de los clientes compran pases “express” que les permiten
saltarse las colas de espera en los juegos. En particular, si un cliente express llega a un juego
siendo usado por un cliente regular, la atención a este ultimo es interrumpida, y se atiende
al cliente express (la atención interrumpida continua una vez ya no hay clientes express
esperando).

d) Cuanto tiempo pasa en promedio un cliente express haciendo cola para subirse a un
juego?

e) Cuanto tiempo pasa en promedio un cliente regular haciendo cola para subirse a un
juego?

Solución parte a) Tenemos N + 1 estaciones (la boletería, más los N juegos). Todas las es-
taciones son M/M/1. Solo existen llegadas externas a la boletería (con tasa λ). Indexando las
estaciones de forma que la estación i corresponde al juego i, para i ≤ N , y la estación N + 1
corresponde a la boletería, tenemos que la matriz de ruteo es
p 1
Pi,j = , i ̸= j ≤ N, PN +1,i = , i ≤ N.
N −1 N
Las tasas efectivas de llegada son las mismas a cada juego (por simetría). Dicha tasa es la solución
a la ecuación (asociada a la estación 1)
N
λ X p
λ̄ = + λ̄ ,
N N −1
i=2

es decir λ̄ = N (1−p) .
λ
Las condiciones de estado estacionario entonces son: i) λ < µ (boletería), y
ii) λ < γN (1 − P ) (los juegos).

202
Solución parte b) Utilizando las formulas de una M/M/1 tenemos que el número promedio de
gente en los juegos (espera más servicio) es

λ
Lparque = N · .
N (1 − p)γ − λ

Entonces, el tiempo esperado de estadía dentro del parque es

1
Wparque = .
(1 − p)γ − λ/N

Solución parte c) El número esperado de veces que alguien se sube a un juego es (1 − p)−1
(esperanza de una Geométrica), y el tiempo promedio en el juego es γ −1 . Entonces, el tiempo
promedio que la gente pasa haciendo colas es
1
Wcolas = Wparque −
(1 − p)γ

Solución parte d) Notamos que los clientes express ignoran a los clientes regulares, por lo que
la respuesta a esta parte es la misma que la de la parte c), pero reemplazando la tasa de llegada
por la asociada a la llegada de clientes express (λ q). Entonces,

express 1 1
Wcolas = − .
(1 − p)γ − q λ/N (1 − p)γ

Solución parte e) Considerando los dos tipos de clientes tenemos que

express regular
Wcolas = q Wcolas + (1 − q) Wcolas .

Con esto, tenemos que

regular 1 q
Wcolas = Wcolas − W express .
1−q 1 − q colas

203