Cadeias de Markov em tempo contínuo
Nesses sistemas, as mudanças não esperam um instante comum para ocorrer. Uma máquina pode falhar antes que outra termine um reparo; um cliente pode chegar enquanto um serviço ainda está em andamento. Para descrever a evolução, precisamos saber quais eventos podem acontecer e quanto tempo se espera por cada um. Alguns modelos ajudam a formular essas perguntas antes de introduzirmos as taxas.
Uma máquina entre operação e reparo. Uma máquina funciona durante algum tempo, falha e é enviada ao reparo. Depois do conserto, volta a funcionar. Seu estado pode registrar apenas se ela está operando ou sendo reparada. Qual é a chance de estar disponível amanhã? Que parcela de um período longo será gasta em reparos?
Uma oficina com duas etapas. Cada carro passa pela funilaria e depois pela pintura. Enquanto um carro é atendido, outros podem chegar e esperar. O número de carros informa o tamanho do trabalho acumulado, mas a etapa atual também importa: terminar a funilaria ainda não libera o carro. Que informação precisamos conservar para descrever a próxima mudança?
Uma população sem gerações sincronizadas. Em uma população, cada indivíduo pode reproduzir-se ou morrer em seu próprio instante. Uma geração já pode estar produzindo descendentes enquanto indivíduos de gerações anteriores continuam vivos. Acompanharemos o total de indivíduos presentes. Como essa população cresce? Em que situações pode desaparecer?
Um serviço que recebe clientes continuamente. Uma chegada aumenta a fila e uma conclusão de serviço a reduz. Com vários atendentes, mais de um serviço pode estar em andamento. Queremos saber como a fila varia, quanto trabalho se acumula e quando a capacidade de atendimento consegue acompanhar as chegadas.
Essas descrições ainda não fixam um modelo probabilístico. Precisaremos especificar os tempos de espera, a independência dos mecanismos e a regra adotada em cada fronteira. A corrida de relógios exponenciais fornecerá uma primeira resposta: qual dos eventos possíveis acontece antes e quanto tempo esperamos por ele? Retomaremos as máquinas, a oficina e a população à medida que as ferramentas forem construídas.
Os relógios exponenciais do Capítulo 5 permitem responder qual evento ocorre primeiro e quanto tempo esperamos por ele. A partir dessas duas informações, construiremos as trajetórias e reuniremos suas taxas em uma matriz, o gerador. As equações de Kolmogorov permitirão calcular as probabilidades de transição; o balanço de fluxos, estudar o equilíbrio. Nos problemas de saída, retomaremos a análise de primeiro passo do tempo discreto, agora levando em conta também a duração da espera. Filas de um ou vários servidores e distribuições explícitas de populações e sistemas de atendimento completam o percurso principal, seguido dos exercícios. Como extensões opcionais, estudaremos redes de Jackson, a propriedade PASTA, o modelo de Jukes–Cantor e aplicações de ramificação, imigração, energia e redundância. A rede da API mostrará como os retornos entre etapas aumentam a carga de um servidor, criando um gargalo mesmo quando há capacidade disponível na entrada. O capítulo de Martingais retomará, em tempo discreto, os problemas de saída e tempos de parada, preparando as aplicações brownianas posteriores.
6.1 Corrida de relógios exponenciais
Em um sistema, uma chegada, uma conclusão de serviço e uma falha podem competir para produzir a próxima mudança. Cada evento tem seu relógio: precisamos saber quando ocorre o primeiro toque e qual relógio o produz. A distribuição exponencial estudada no Capítulo 5 permite responder às duas perguntas e recomeçar o cálculo depois de cada evento.
Sejam \(S\sim \operatorname {Exp}(\lambda )\) e \(T\sim \operatorname {Exp}(\mu )\) independentes. Para que o mínimo de \(S\) e \(T\) seja maior que \(t\geq 0\), ambos devem exceder \(t\). Portanto,
Logo, \(\min (S,T)\sim \operatorname {Exp}(\lambda +\mu )\). Para descobrir qual relógio toca primeiro, integramos a densidade de \(S\) multiplicada pela probabilidade de \(T\) ainda não ter terminado naquele instante:
A última integral vale um, pois seu integrando é a densidade de uma exponencial de taxa \(\lambda +\mu \).
Ana e Beatriz chegam simultaneamente a um salão. O tempo da manicure de Ana é exponencial com média de 20 minutos, e o corte de cabelo de Beatriz é exponencial com média de 30 minutos. Suponha os tempos independentes. (a) Qual é a probabilidade de Ana terminar primeiro? (b) Qual é o tempo esperado até que ambas tenham terminado?
As taxas são \(1/20\) e \(1/30\) por minuto. Portanto, Ana termina primeiro com probabilidade
\[ \frac{1 / 20}{1 / 20+1 / 30}=\frac{30}{30+20}=\frac{3}{5}. \]A taxa do primeiro término é \(1/20+1/30=5/60\), de modo que o tempo médio até alguém terminar é 12 minutos. Se Ana termina primeiro, o tempo residual de Beatriz ainda tem média 30 minutos; se Beatriz termina primeiro, o tempo residual de Ana tem média 20 minutos. Condicionando em quem termina primeiro, o tempo esperado até que ambas tenham terminado é
\[ 12+(3 / 5) \cdot 30+(2 / 5) \cdot 20=12+18+8=38. \]
Podemos conferir a média sem separar os dois casos. Para quaisquer números reais, \(\max (S,T)=S+T-\min (S,T)\); logo, aqui,
O teorema seguinte também justificará a afirmação sobre as esperas residuais dos relógios que ainda não tocaram.
O mesmo raciocínio vale para qualquer número finito de relógios exponenciais independentes. O resultado seguinte reúne a lei do primeiro toque, a identidade do vencedor e as esperas que restam nos demais relógios.
Corrida de exponenciais Sejam \(T_1,\ldots ,T_n\) independentes, com \(T_i\sim \operatorname {Exp}(\lambda _i)\) e \(\lambda _i\gt 0\). Defina \(V=\min (T_1,\ldots ,T_n)\) e seja \(I\) o índice do relógio que toca primeiro. Então
Além disso, \(I\) e \(V\) são independentes. Condicionado a \(I=i\), os tempos residuais \(T_j-V\), \(j\ne i\), são exponenciais independentes, com suas taxas originais \(\lambda _j\), e são independentes de \(V\).
Ponha \(\Lambda =\sum _i\lambda _i\). Pela independência,
Logo, \(V\) é exponencial de taxa \(\Lambda \). Dois relógios independentes com densidades contínuas empatam com probabilidade zero. Como há apenas um número finito de pares, o vencedor \(I\) está bem definido quase certamente.
Fixe \(i\) e um intervalo \(0\le a\lt b\). Para que o relógio \(i\) vença em um instante \(v\) desse intervalo, os demais devem exceder \(v\). Integrando sobre o instante do toque de \(i\),
Deixar \(b\) crescer e tomar \(a=0\) dá \(\mathbb P(I=i)=\lambda _i/\Lambda \). A mesma fatoração para todos os intervalos mostra que o vencedor e o instante \(V\) são independentes.
Para examinar os relógios que perderam, fixe números \(u_j\ge 0\) para \(j\ne i\). Se \(I=i\) e \(V=v\), pedir que cada espera residual exceda \(u_j\) equivale a exigir \(T_j\gt v+u_j\). Assim,
Os fatores à direita são as probabilidades de cauda de exponenciais independentes com as taxas originais. Como a igualdade vale para quaisquer limites \(u_j\) e qualquer intervalo \((a,b]\), as esperas residuais são independentes entre si e de \(V\), condicionado ao vencedor \(I=i\). Para \(n=1\), o produto vazio vale \(1\).
Um submarino possui três dispositivos independentes, cujos tempos de falha são exponenciais com médias de \(1\), \(3/2\) e \(3\) anos. Ele deve retornar quando ocorrer a segunda falha. Denote os dispositivos por \(A,B,C\); suas taxas são, respectivamente, \(1\), \(2/3\) e \(1/3\) por ano.
O primeiro tempo de falha tem taxa total \(1+2/3+1/3=2\) e, portanto, média \(1/2\). Os dispositivos \(A\), \(B\) e \(C\) falham primeiro com probabilidades \(1/2\), \(1/3\) e \(1/6\). Se \(A\) falha primeiro, a taxa dos relógios restantes é \(1\), com espera média \(1\). Se \(B\) falha primeiro, a taxa é \(4/3\), com média \(3/4\); se \(C\) falha primeiro, a taxa é \(5/3\), com média \(3/5\). Condicionando em qual deles falhou primeiro, o tempo médio adicional até a segunda falha é
Logo, o tempo médio de operação é
Para calcular uma ordem de falhas, multiplicamos a probabilidade do primeiro vencedor pela probabilidade condicional do segundo. Por exemplo,
As seis probabilidades, na ordem \(ABC,ACB,BAC,BCA,CAB,CBA\), são
Sua soma é \(1\), uma verificação rápida de que nenhuma ordem foi esquecida.
Recomeçar a corrida após um evento.
Retomemos o Exemplo 5.10, com chegadas vermelhas de taxa \(\lambda \) e verdes de taxa \(\mu \). A próxima chegada é vermelha com probabilidade \(p=\lambda /(\lambda +\mu )\) e verde com probabilidade \(1-p\), pela corrida dos dois relógios exponenciais. Após cada chegada, o relógio que tocou é reiniciado com uma espera exponencial nova, da mesma taxa. O relógio que perdeu conserva sua espera residual, que pela falta de memória é exponencial com a taxa original, independente da nova espera. Isso vale tanto se a chegada anterior foi vermelha quanto se foi verde: o par de esperas volta sempre a ter a lei conjunta de duas variáveis exponenciais independentes de taxas \(\lambda \) e \(\mu \), independentemente do tempo e da cor anteriores. Consequentemente, a próxima cor tem novamente probabilidade \(p\) de ser vermelha, sem depender das chegadas anteriores. As cores sucessivas são, portanto, Bernoulli independentes.
Essa interpretação por relógios recupera a conclusão obtida por afinamento no capítulo anterior. Nos modelos seguintes, a mesma regra determinará tanto a espera até uma mudança quanto a escolha do evento que a produz.
6.2 Definições e exemplos
No Capítulo 2 o tempo assumia valores inteiros. Agora o parâmetro é \(t\geq 0\), uma descrição mais natural para chegadas, falhas, serviços e reações.
A propriedade de Markov continua sendo a mesma: conhecido o estado atual, o passado não acrescenta informação para prever o futuro. O que muda é o relógio. Como o tempo varia continuamente, descrever apenas a probabilidade do “próximo passo” já não basta; precisamos dizer também quanto se espera até esse passo.
Cadeia de Markov homogênea em tempo contínuo Um processo \((X_t)_{t\geq 0}\) com espaço de estados contável \(S\) é uma cadeia de Markov homogênea em tempo contínuo se, para \(0\leq s_0\lt \cdots \lt s_n\lt s\), \(t\geq 0\) e escolhas de estados para as quais os condicionamentos tenham probabilidade positiva,
Comecemos por modelos já conhecidos, agora observados com outro relógio. Em cada um deles, as taxas indicam quais mudanças são possíveis e com que frequência elas são tentadas. Depois construiremos a trajetória diretamente a partir dessas taxas.
Há um cuidado aqui: observar apenas \(X\) até o instante \(s\) não revela quantos toques o relógio deu, pois um passo de \(Y\) pode conservar o estado. Condicionemos, então, numa informação maior: toda a trajetória de \(N\) até \(s\) e os estados \(Y_0,\ldots ,Y_m\), onde \(m=N(s)\) e \(Y_m=i\). Pelos incrementos independentes do processo de Poisson, \(N(s+t)-N(s)\) tem lei \(\operatorname {Poisson}(\lambda t)\), independente desse histórico. Pela propriedade de Markov, os próximos passos de \(Y\) dependem dele apenas por \(Y_m=i\). Assim, mesmo com essa informação adicional, a probabilidade de observar \(X_{s+t}=j\) é
Como a expressão depende do histórico somente por \(X_s=i\), isso também vale quando conhecemos apenas o passado de \(X\). Para \(s=0\) obtemos a fórmula de \(P_t\) no enunciado.
Equação de Chapman–Kolmogorov Para uma cadeia homogênea, \(s,t\geq 0\) e \(i,j\in S\),
Os eventos \(\{ X_s=k\} \), com \(k\in S\), formam uma partição das trajetórias no instante intermediário. Decompondo segundo esse estado, temos
Usando a definição de probabilidade condicional e a propriedade de Markov, a expressão anterior torna-se
Se um estado \(k\) tem probabilidade zero no instante \(s\), sua parcela é zero e não precisamos definir uma probabilidade condicional sobre esse evento. As demais parcelas usam exatamente a propriedade de Markov e a homogeneidade temporal. Como são não negativas, a soma é bem definida também quando \(S\) é enumerável. Isso dá \(P_{s+t}=P_sP_t\).
A equação de Chapman–Kolmogorov sugere que as probabilidades de transição podem ser recuperadas de seu comportamento infinitesimal em \(0\).
Escolher um estado que conserve a informação necessária para a próxima mudança. Em uma oficina, isso pode exigir a etapa do serviço, além do número de carros.
Listar os eventos que podem ocorrer a partir desse estado e identificar o estado produzido por cada um.
Atribuir a cada evento sua taxa. Quando eventos distintos levam ao mesmo destino, suas taxas se somam, pela corrida de relógios.
Somar as taxas das mudanças reais de estado e colocar o oposto dessa soma na diagonal. Um evento que conserva o estado não entra nessa soma; ele pode aparecer como um toque sem salto na uniformização.
Se \(N(h)\) conta os toques de um relógio de Poisson de taxa \(\lambda \), então a probabilidade de dois ou mais toques pode ser limitada sem uma expansão de Taylor:
Usamos \(\mathbf1_{\{ N(h)\ge 2\} }\le N(h)(N(h)-1)/2\) e a fórmula já demonstrada para os momentos fatoriais da Poisson. Em particular, ao dividir essa probabilidade por \(h\), o resultado tende a zero.
Para \(j\ne i\), se houver exatamente um toque, a cadeia passa de \(i\) a \(j\) com probabilidade \(U(i,j)\). Se houver dois ou mais, a contribuição total é no máximo a probabilidade acima. Portanto,
Dividindo por \(h\) e fazendo \(h\downarrow 0\), encontramos \(q(i,j)=\lambda U(i,j)\) para \(j\ne i\). No caso diagonal, um toque pode conservar o estado; como a soma de cada linha de \(U\) é \(1\), a taxa total de saída real é
Portanto o relógio de eventos toca à taxa \(\lambda \), mas nem todo toque corresponde a uma mudança do estado.
Seja \(X_t\) o número de chegadas até o instante \(t\) em um processo de Poisson de taxa \(\lambda \). A contagem permanece no estado \(n\) até a próxima chegada; quando ela ocorre, passa necessariamente a \(n+1\). Como a espera é exponencial de taxa \(\lambda \),
Não há saltos para estados menores nem para \(n+2\) diretamente. A taxa não depende de \(n\): esperar a próxima chegada quando já ocorreram cem eventos tem a mesma lei que esperar a primeira.
Imagine um banco com \(s\) caixas. Quando todos estão ocupados, os clientes aguardam em uma fila única. Suponha que as chegadas formem um processo de Poisson de taxa \(\lambda \) e que os tempos de serviço sejam exponenciais independentes de taxa \(\mu \). Como no Exemplo 6.5, \(q(n,n+1)=\lambda \). Para modelar as saídas, consideramos a taxa total de conclusão dos serviços.
Se há menos de \(s\) clientes, todos recebem serviço, e cada um contribui com um relógio de taxa \(\mu \); a taxa total de conclusão é \(n\mu \). Com \(s\) ou mais clientes, todos os caixas estão ocupados e a taxa se estabiliza em \(s\mu \). Assim, aumentar a fila não aumenta indefinidamente a capacidade de atendimento. É a corrida de relógios exponenciais estudada na Seção 6.1.
Retomemos a população da Seção 4.3, mas sem esperar que todos os indivíduos se reproduzam ao mesmo tempo. Cada indivíduo gera um novo indivíduo à taxa \(\lambda \) e morre à taxa \(\mu \), independentemente dos demais. Quando há \(n\) indivíduos, existem \(n\) relógios de nascimento e \(n\) relógios de morte. A soma de suas taxas dá
A população muda uma unidade por vez. A espera até a próxima mudança tem média \(1/[n(\lambda +\mu )]\), quando \(\lambda +\mu \gt 0\): populações maiores mudam mais rapidamente. Já a probabilidade de a próxima mudança ser um nascimento é \(\lambda /(\lambda +\mu )\), independentemente de \(n\).
O estado zero é absorvente. Se \(\mu =0\), a população nunca diminui e obtemos o processo de Yule.
6.2.1 Escolher o estado antes de escrever as taxas
Antes de escrever uma taxa, precisamos saber a partir de qual estado o evento pode ocorrer. Os dois modelos a seguir retomam as máquinas e a oficina da abertura. Em ambos, uma descrição aparentemente suficiente — o número de máquinas funcionando ou de carros na oficina — pode omitir informação necessária para determinar a próxima mudança.
Duas máquinas operam simultaneamente. Enquanto funciona, a máquina \(i\) falha com taxa \(\lambda _i\gt 0\), para \(i=1,2\). Um único técnico repara a máquina que falhou, com tempo exponencial de taxa \(\mu \gt 0\). Se as duas máquinas ficarem avariadas, o sistema é desligado definitivamente e os reparos são interrompidos. Todos os tempos novos de falha e reparo são independentes. As taxas são medidas na mesma unidade inversa de tempo.
Registremos separadamente as duas máquinas. O valor \(1\) indica operação e \(0\), avaria. Usaremos os estados
Em \(B\), a máquina 1 funciona e a máquina 2 está em reparo; em \(C\) ocorre o contrário. O estado \(F\) representa o desligamento definitivo.
Em \(A\), competem os dois relógios de falha. A falha da máquina 2 leva a \(B\), com taxa \(\lambda _2\), e a da máquina 1 leva a \(C\), com taxa \(\lambda _1\). A espera pelo primeiro evento é exponencial de taxa \(\lambda _1+\lambda _2\). Não existe uma transição direta \(A\to F\): as falhas são independentes e não ocorrem simultaneamente com probabilidade positiva.
Em \(B\), o reparo da máquina 2 compete com a falha da máquina 1. O reparo leva a \(A\), com taxa \(\mu \), e a falha leva a \(F\), com taxa \(\lambda _1\). Portanto a espera é exponencial de taxa \(\mu +\lambda _1\). Em \(C\), as mesmas alternativas têm taxas \(\mu \) e \(\lambda _2\). Em \(F\), a regra do modelo não permite novas mudanças. Na ordem \((A,B,C,F)\), obtemos
Cada diagonal é o negativo da soma das demais entradas de sua linha. As entradas nulas também dizem algo sobre o modelo: em um único evento, não se passa de \(B\) para \(C\), nem se troca uma máquina avariada por outra. Essas mudanças exigiriam mais de um evento.
Conhecidos \(B\) ou \(C\), não precisamos guardar há quanto tempo o reparo começou. A falta de memória conserva sua lei exponencial; a mesma propriedade vale para a máquina que continua funcionando. Isso justifica usar os quatro estados, sem acrescentar idades aos relógios.
Podemos guardar somente o número de máquinas funcionando? Se \(\lambda _1=\lambda _2=\lambda \), os estados \(B\) e \(C\) têm a mesma taxa \(\lambda \) para o desligamento e a mesma taxa \(\mu \) para voltar a duas máquinas em operação. O número \(N_t\) de máquinas funcionando é, então, uma cadeia nos estados \(0,1,2\), com gerador
A taxa \(2\lambda \) vem dos dois relógios de falha quando ambas funcionam. Em zero, o sistema continua absorvido: a agregação não muda a regra de desligamento.
Com taxas de falha diferentes, essa redução em geral não é válida. Partindo de \(A\), a primeira falha deixa o sistema em \(B\) com probabilidade \(w=\lambda _2/(\lambda _1+\lambda _2)\) e em \(C\) com probabilidade \(1-w\). Se \(H\) é o tempo da permanência seguinte com uma única máquina funcionando, sua sobrevivência é
O observador que guarda apenas \(N_t=1\) não sabe qual dos dois relógios de falha está ativo. Para ver que a espera resultante não tem falta de memória, fixe \(s\gt 0\) e expanda o quadrado de \(u(s)\):
quando \(\lambda _1\ne \lambda _2\). Uma espera sem memória satisfaria \(u(2s)=u(s)^2\). O tempo já transcorrido fornece informação sobre qual máquina provavelmente permanece em operação; o número de máquinas, sozinho, perdeu informação necessária.
Uma oficina recebe carros segundo um processo de Poisson de taxa \(\lambda \gt 0\). Um único profissional atende os carros por ordem de chegada. Para cada carro, primeiro faz a funilaria, com duração exponencial de taxa \(\mu _F\gt 0\), e depois a pintura, com duração exponencial de taxa \(\mu _P\gt 0\). Só depois da pintura o carro sai e, se houver outro esperando, sua funilaria começa imediatamente. As durações das etapas são independentes entre si, entre carros e das chegadas.
O estado vazio será denotado por \(0\). Quando há carros, escrevemos \((n,F)\) ou \((n,P)\): \(n\geq 1\) é o total de carros na oficina e a letra identifica a etapa do carro em atendimento. Todos os carros em espera ainda precisam iniciar a funilaria. O espaço de estados é
Essa descrição evita estados artificiais como “oficina vazia com uma pintura em andamento”.
Na oficina vazia, só uma chegada muda o estado:
Em \((n,F)\), competem a próxima chegada e a conclusão da funilaria. A chegada conserva o carro em atendimento e sua etapa; a conclusão da funilaria inicia a pintura do mesmo carro. Portanto,
Em \((n,P)\), uma chegada também aumenta apenas o total. Quando a pintura termina, um carro sai. Se \(n\geq 2\), o próximo começa a funilaria; se \(n=1\), a oficina fica vazia:
Todas as demais taxas entre estados distintos são zero. A taxa de saída de um estado é a soma dos dois relógios que podem tocá-lo. A falta de memória permite usar a etapa atual sem registrar seu tempo já decorrido.
O total \(n\) sozinho, em geral, não fornece essa informação. Se a etapa é pintura, a chance de uma saída em um intervalo de comprimento \(h\) é \(\mu _P h+o(h)\). Se a etapa é funilaria, uma saída exige concluir duas etapas nesse intervalo. Sua probabilidade é no máximo
pois ambas as durações precisam ser menores que \(h\). A taxa de uma saída imediata depende, portanto, da etapa escondida. Além disso, o tempo total de serviço é a soma de duas exponenciais, não uma única espera exponencial. Guardar a fase recupera uma descrição de Markov.
6.2.2 Construção a partir das taxas
Nos exemplos anteriores, especificamos o modelo por meio das taxas \(q(i,j)\). Agora vamos transformar essas taxas em uma trajetória. A construção separa duas perguntas: por quanto tempo a cadeia permanece no estado atual e para onde ela vai quando sai.
Informalmente, ao chegar a \(i\) a cadeia liga um relógio exponencial de taxa \(\lambda _i\). Quando esse relógio toca, escolhe o próximo estado segundo a linha \(r(i,\cdot )\) e repete o procedimento.
Para formalizar, seja \((Y_n)_{n\geq 0}\) a cadeia de Markov em tempo discreto com matriz \(R\), chamada de cadeia de saltos. Sejam \(E_0,E_1,\ldots \) exponenciais de taxa 1, independentes entre si e de \(Y\). Quando \(\lambda _{Y_n}\gt 0\), ponha
Então \(\tau _{n+1}\) é exponencial de taxa \(\lambda _{Y_n}\), e definimos
Se a cadeia alcança um estado com taxa de saída zero, ela permanece ali para sempre.
Fixe um instante determinístico \(s\geq 0\) e um estado \(i\) com \(\lambda _i\gt 0\). Para verificar a propriedade de Markov, precisamos levar em conta não só o estado observado, mas também tudo o que aconteceu antes de \(s\).
Decomponha a situação \(\{ X_s=i\} \) segundo os eventos
Em cada um desses eventos, consideramos os estados já visitados, \(Y_0,\ldots ,Y_n\), e as esperas já concluídas, \(\tau _1,\ldots ,\tau _n\). Essa história não inclui o próximo destino \(Y_{n+1}\) nem o relógio \(E_n\), que determina a permanência atual. Conhecemos \(T_n\); saber que ainda estamos em \(i\) no instante \(s\) acrescenta apenas a informação \(\tau _{n+1}\gt s-T_n\). Como a próxima espera é exponencial de taxa \(\lambda _i\), independente da história anterior, para todo \(u\geq 0\),
Para reunir as histórias, integramos essa conta contra as densidades das esperas concluídas, como na construção do processo de Poisson. O fator \(e^{-\lambda _i u}\) não depende dos seus valores. Assim, mesmo conhecendo a duração já transcorrida da permanência, a espera restante tem lei \(\operatorname {Exp}(\lambda _i)\).
Além disso, pela propriedade de Markov da cadeia de saltos \(Y\) e pela independência dos relógios, o próximo destino tem distribuição \(r(i,\cdot )\) e os sorteios posteriores recomeçam com a mesma regra, sem depender daquela história. Isso vale em cada um dos eventos da decomposição; somando sobre \(n\), a evolução após \(s\) depende do passado apenas por \(X_s=i\).
Se \(\lambda _i=0\), o estado é absorvente. No caso de explosão, o estado cemitério também é absorvente. Portanto, a propriedade de Markov vale para a cadeia construída, como afirmado. Para verificar os limites, partimos de \(i\) com \(\lambda _i\gt 0\). Se os dois primeiros saltos ocorrem até \(h\), então ambas as esperas são menores que \(h\), pois
Condicionado ao primeiro destino \(k\), as esperas são independentes, com taxas \(\lambda _i\) e \(\lambda _k\). Se \(k\) é absorvente, não há segundo salto. Ao somar sobre os destinos, obtemos a cota
Escreva
Para cada \(k\), a finitude de \(\lambda _k\) dá \(1-e^{-\lambda _k h}\to 0\) quando \(h\downarrow 0\). Além disso,
e os pesos \(r(i,k)\) somam 1. Dado \(\varepsilon \gt 0\), escolha um conjunto finito \(F\) de destinos tal que \(\sum _{k\notin F}r(i,k)\lt \varepsilon /2\). Nos destinos de \(F\), cada parcela tende a zero; logo, para \(h\) suficientemente pequeno, \(\sum _{k\in F}r(i,k)(1-e^{-\lambda _kh})\lt \varepsilon /2\). A parcela fora de \(F\) é menor que \(\varepsilon /2\), pois \(1-e^{-\lambda _kh}\leq 1\). Portanto \(A(h)\to 0\) por um argumento de soma finita e cauda. Não é necessário supor que as taxas \(\lambda _k\) sejam uniformemente limitadas: a finitude estado a estado é suficiente neste passo. Como
e \(A(h)\to 0\), a probabilidade de dois ou mais saltos, limitada pelo produto dessas duas quantidades, é \(o(h)\). De fato, ao dividir o produto por \(h\), o primeiro fator tende a \(\lambda _i\) e o segundo tende a zero.
A chance de o primeiro salto ir a \(j\) até \(h\) é \((1-e^{-\lambda _i h})r(i,j)=q(i,j)h+o(h)\). Para \(j\ne i\), a diferença entre esse evento e \(\{ X_h=j\} \) só pode ocorrer em caminhos com pelo menos dois saltos: ou o primeiro salto foi a \(j\) e a cadeia voltou a sair, ou ela chegou a \(j\) depois de passar por outro estado. A diferença das probabilidades é, portanto, \(o(h)\), e \(P_h(i,j)=q(i,j)h+o(h)\).
Para a diagonal, a ausência de salto tem probabilidade \(e^{-\lambda _i h}\). Sair de \(i\) e estar novamente em \(i\) até \(h\) exige pelo menos dois saltos. Assim,
Dividir as diferenças por \(h\) fornece todos os limites do gerador. Se \(\lambda _i=0\), a trajetória permanece em \(i\) e os limites são imediatos.
Pode acontecer de \(T_n\) convergir para um valor finito \(T_\infty \). Nesse caso, a cadeia realiza infinitos saltos em tempo finito; dizemos que ocorre uma explosão. Para completar a trajetória depois de \(T_\infty \), acrescentamos um estado cemitério \(\Delta \) e definimos \(X_t=\Delta \) para \(t\geq T_\infty \). O próximo exemplo mostra que explosões não são apenas uma possibilidade abstrata.
Sejam \(\lambda \gt 0\) e \(p\in \mathbb R\). Suponha que a cadeia comece em 1 e que
sem outros saltos. O tempo \(\tau _i\) passado no estado \(i\) é exponencial de taxa \(\lambda i^p\), e os tempos \(\tau _i\) podem ser tomados independentes. Logo,
é o instante em que a cadeia deixa o estado \(n\).
O processo explode quase certamente se \(p\gt 1\) e não explode se \(p\leq 1\).
Se \(p\gt 1\), então
Para explicitar a última implicação, a desigualdade de Markov dá \(\mathbb P(T_\infty \gt M)\leq E(T_\infty )/M\). Ao fazer \(M\to \infty \), obtemos \(\mathbb P(T_\infty =\infty )=0\). Portanto, o processo explode quase certamente.
Quando \(p=1\), caso do processo de Yule,
Ainda precisamos mostrar que as flutuações não anulam esse crescimento. Como
a desigualdade de Chebyshev fornece
Para cada \(M\lt \infty \), quando \(E(T_n)/2\gt M\), \(\mathbb {P}(T_\infty \leq M)\leq \mathbb {P}(T_n\leq M)\leq 4C/E(T_n)^2\to 0\). Tomando a união sobre \(M\) inteiro, obtemos \(T_\infty =\infty \) quase certamente. Para \(p\lt 1\), use os mesmos \(E_i\sim \operatorname {Exp}(1)\): \(E_i/(\lambda i^p)\geq E_i/(\lambda i)\) para \(i\geq 1\). As esperas são maiores que no caso \(p=1\), portanto também não há explosão.
Se todas as taxas são zero, a trajetória é constante. Caso contrário, suponha \(0\lt \Lambda =\sup _i\lambda _i\lt \infty \) e defina
Em palavras, a partir de cada estado são feitas tentativas de salto à taxa \(\Lambda \), mas a cadeia permanece no mesmo estado com probabilidade \(1-\lambda _i/\Lambda \), de modo que a taxa de saída do estado \(i\) é \(\lambda _i\). Se \(Y_n\) for uma cadeia de Markov com probabilidades de transição \(U(i,j)\) e \(N(t)\) for um processo de Poisson de taxa \(\Lambda \), independente de \(Y\), então \(X_t=Y_{N(t)}\) terá as taxas de transição desejadas. A trajetória dá no máximo \(N(t)\) mudanças até \(t\), logo não explode. A mesma construção fundamenta as equações a seguir.
6.3 Calculando as probabilidades de transição
Conhecer uma taxa responde a uma pergunta local. Para prever o estado daqui a uma hora, precisamos somar caminhos com diferentes números de saltos. As equações de Kolmogorov organizam essa soma. Começaremos pelo caso finito, em que a exponencial de uma matriz fornece uma descrição completa.
Se todas as taxas forem nulas, então \(Q=0\) e \(P_t=I\). Caso contrário, escolha \(\Lambda \ge \max _i\lambda _i\), com \(\Lambda \gt 0\), e defina \(U=I+Q/\Lambda \). Essa matriz possui entradas não negativas e linhas de soma \(1\); portanto é uma matriz de transição.
Vamos construir a cadeia com um relógio de Poisson de taxa \(\Lambda \). A cada toque, aplicamos uma transição segundo \(U\). Alguns toques deixam o estado inalterado. Quando estamos em \(i\), a probabilidade de que um toque produza uma mudança real é \(\lambda _i/\Lambda \). Logo, a probabilidade de nenhuma mudança real até \(t\) é
A espera até a próxima mudança é, portanto, exponencial de taxa \(\lambda _i\). Quando ela acontece, o destino \(j\ne i\) tem probabilidade
Isso concorda com a construção por taxas (quando \(\lambda _i=0\), o estado permanece absorvente). A independência dos novos toques permite recomeçar a mesma regra depois de cada mudança real.
Condicionando ao número de toques até \(t\), obtemos
Cada entrada de \(U^n\) está entre zero e um; por comparação com a série exponencial usual, podemos derivar termo a termo em intervalos limitados:
Como \(P_t\) é soma de potências de \(U\), comuta com \(U\) e, portanto, com \(Q=\Lambda (U-I)\). Isso também dá \(P_t'=QP_t\); a condição inicial é \(P_0=I\).
Finalmente, expandimos \(U^n=(I+Q/\Lambda )^n\) pela fórmula binomial e reagrupamos:
A troca das somas é válida porque o espaço é finito: se \(M=\max _i\sum _j|q(i,j)|\), cada entrada de \(Q^k\) tem módulo no máximo \(M^k\). Assim, os valores absolutos são dominados por séries exponenciais.
Extensão a espaços enumeráveis* O argumento por uniformização também funciona em um espaço enumerável, desde que as taxas de saída tenham um limite comum \(\Lambda =\sup _i\lambda _i\lt \infty \). Se \(\Lambda \gt 0\), escreva \(U=I+Q/\Lambda \). Como na prova anterior,
Para cada \(i,j\) temos \(0\le U^n(i,j)\le 1\). Assim, a série e sua série de derivadas são dominadas, em qualquer intervalo \(0\le t\le b\), pelas séries exponenciais escalares correspondentes. Podemos, portanto, derivar termo a termo.
A associatividade das multiplicações e a não negatividade das parcelas dão
As duas somas convergem absolutamente: na primeira, as parcelas são limitadas por \(P_t(i,k)\); na segunda, por \(U(i,k)\). Cada uma dessas famílias de pesos soma \(1\). Como \(Q=\Lambda (U-I)\), obtemos ambas as equações de Kolmogorov também neste caso. Se \(\Lambda =0\), a cadeia não salta e \(P_t=I\).
Para cadeias finitas, e também sob as hipóteses da extensão opcional, as duas equações assumem em coordenadas a forma
No caso finito, as somas têm um número finito de termos; na extensão enumerável, elas são absolutamente convergentes. Matrizes em geral não comutam; aqui \(P_t\) é construído a partir de potências de \(Q\) ou de \(I+Q/\Lambda \). Com taxas não limitadas, existem versões mais gerais, mas elas exigem justificativas próprias. Não aplicaremos esses enunciados fora de suas hipóteses.
Na abertura, uma máquina alternava entre funcionamento e reparo. Usaremos o estado \(1\) para funcionamento e o estado \(2\) para reparo. A taxa \(\lambda \) mede as falhas quando ela funciona; a taxa \(\mu \) mede as conclusões de reparo quando ela está parada. A falta de memória das esperas exponenciais permite conservar apenas esse estado.
Considere \(S=\{ 1,2\} \), com taxas positivas \(\lambda \) de \(1\) para \(2\) e \(\mu \) de \(2\) para \(1\), medidas na mesma unidade inversa de tempo. Então
Escrevendo \(r=\lambda +\mu \), a matriz de transição é
Pela equação progressiva e pela identidade que soma cada linha de \(P_t\), temos, para \(a=1,2\),
Para resolver a equação, subtraia o valor constante \(\mu /r\) e ponha \(z_a(t)=P_t(a,1)-\mu /r\). Então \(z_a'(t)=-rz_a(t)\), de modo que \(z_a(t)=z_a(0)e^{-rt}\). Portanto,
Usar \(P_0(1,1)=1\) e \(P_0(2,1)=0\) fornece a primeira coluna. Como \(P_t(a,1)+P_t(a,2)=1\), a segunda coluna é o complemento da primeira em cada linha. Finalmente, \(e^{-rt}\to 0\) porque \(r\gt 0\), e as duas linhas tendem a \((\mu /r,\lambda /r)\).
O termo exponencial mede quanto da informação sobre o estado inicial ainda permanece.
6.4 Comportamento limite
Daqui em diante, supomos que as cadeias consideradas sejam não explosivas. Assim, a trajetória permanece no espaço de estados em todo tempo finito e as probabilidades de transição conservam massa total 1.
Os tempos exponenciais permitem permanecer no estado atual por qualquer duração finita, com probabilidade positiva. Ao observar a cadeia a cada \(h\) unidades de tempo, essa permanência elimina a obstrução da periodicidade. Ainda precisamos de irredutibilidade e de uma distribuição estacionária para obter convergência ao equilíbrio.
Positividade das transições Se \(X_t\) é irredutível e \(t\gt 0\), então \(P_t(i,j)\gt 0\) para todos os estados \(i,j\).
Se \(i=j\), basta considerar a possibilidade de não sair desse estado: \(P_t(i,i)\geq e^{-\lambda _i t}\gt 0\). Para \(i\ne j\), escolha um caminho \(i=k_0,k_1,\ldots ,k_n=j\) com taxas positivas. Para cada uma das suas arestas, \(P_h(k_{m-1},k_m)/h\to q(k_{m-1},k_m)\gt 0\). Como há apenas um número finito de arestas, podemos escolher um mesmo \(h\gt 0\) suficientemente pequeno para que
para todo \(m\), e ainda exigir \(nh\lt t\). Ao aplicar repetidamente Chapman–Kolmogorov, a probabilidade total contém, entre suas parcelas não negativas, a de passar por \(k_m\) no instante \(mh\). Depois disso, podemos permanecer em \(j\) durante o tempo restante, com probabilidade ao menos \(e^{-\lambda _j(t-nh)}\gt 0\). Portanto,
Verificar a definição diretamente exigiria conhecer \(P_t\) em todos os tempos. Com taxas de saída limitadas, o gerador oferece um teste local.
Ponha \(\Lambda =\sup _i\lambda _i\). Se \(\Lambda =0\), então \(Q=0\), a cadeia não muda de estado e toda distribuição é estacionária. Suponha \(\Lambda \gt 0\) e defina
Se \(\pi Q=0\), então \(\pi U=\pi \) e, por indução, \(\pi U^n=\pi \) para todo \(n\). Pela uniformização,
Portanto, \(\pi \) é estacionária.
Para a recíproca, basta olhar um intervalo muito curto. Na representação por um relógio Poisson de taxa \(\Lambda \), separe os casos de zero, um e pelo menos dois toques:
O resto \(R_t(i,j)\ge 0\) corresponde a dois ou mais toques e satisfaz
A última desigualdade usa \(\mathbf1_{\{ N\ge 2\} }\le N(N-1)/2\) e \(E[N(N-1)]=(\Lambda t)^2\) para uma Poisson.
Se \(\pi \) é estacionária, multiplique essa identidade por \(\pi (i)\) e some em \(i\). A contribuição do resto não excede \((\Lambda t)^2/2\), mesmo em um espaço enumerável, pois as massas \(\pi (i)\) somam \(1\). Em cada coordenada \(j\) obtemos
Isso prova \(\pi Q=0\), sem derivar séries de matrizes infinitas.
Retomemos a máquina do Exemplo 6.13. O estado \(1\) indica funcionamento e o estado \(2\), reparo. Uma máquina em funcionamento falha à taxa \(\lambda \gt 0\); uma máquina em reparo volta a funcionar à taxa \(\mu \gt 0\). Queremos saber a probabilidade de encontrá-la funcionando em um instante de equilíbrio.
Como o espaço tem apenas dois estados, podemos usar o Lema 6.6. A primeira coordenada de \(\pi Q=0\) é
O fluxo de falhas, \(\lambda \pi (1)\), deve compensar o fluxo de reparos concluídos, \(\mu \pi (2)\). Substituindo \(\pi (2)=1-\pi (1)\), obtemos
A segunda coordenada de \(\pi Q=0\) é a mesma equação com sinal trocado; portanto não impõe uma condição adicional. As duas massas são positivas e somam um, de modo que a distribuição encontrada é estacionária.
Se o funcionamento dura, em média, oito dias e o reparo dura dois, as taxas por dia são \(\lambda =1/8\) e \(\mu =1/2\). Logo,
Em equilíbrio, a probabilidade de encontrar a máquina disponível é \(4/5\). Esse número é chamado de disponibilidade em equilíbrio. Ele não é a probabilidade de atravessar um intervalo inteiro sem falhar: uma máquina pode falhar, ser reparada e estar funcionando no instante em que a consultamos.
Essa distinção aparece em duas contas. Partindo do funcionamento, a fórmula de \(P_t\) já obtida fornece
com \(t\) medido em dias. Já não ocorrer nenhuma falha até \(t\) significa que a primeira espera exponencial ainda não terminou; sua probabilidade é
A primeira probabilidade tende a \(4/5\); a segunda tende a zero. Disponibilidade em uma data e funcionamento sem interrupção respondem a perguntas diferentes sobre o mesmo modelo.
Podemos também responder à pergunta da abertura sobre a fração do tempo gasta em reparos. Comecemos com a máquina funcionando. No ciclo \(j\), sejam \(U_j\) a duração do funcionamento e \(D_j\) a duração do reparo seguinte. Pela construção com novos relógios independentes, os pares \((U_j,D_j)\) são independentes e têm a mesma lei, com \(EU_j=1/\lambda \) e \(ED_j=1/\mu \). Para acompanhar os ciclos completos, escrevemos
O instante \(S_n\) encerra o ciclo \(n\), e \(R_n\) é o tempo de funcionamento acumulado até ele. Pela lei forte dos grandes números,
Portanto \(S_n\to \infty \). Se \(R(t)\) é o tempo total de funcionamento até \(t\) e \(S_n\leq t\lt S_{n+1}\), então, para \(n\geq 1\),
Os dois extremos têm o mesmo limite: basta dividir numeradores e denominadores por \(n\) e usar \((n+1)/n\to 1\) nas somas com índice \(n+1\). Como o ciclo que contém \(t\) tem índice crescente quando \(t\to \infty \), a desigualdade fornece
A fração de tempo em reparo é o complemento, cujo limite é \(\lambda /(\lambda +\mu )\). No caso numérico, as frações observadas ao longo de uma realização tendem, portanto, a \(4/5\) em funcionamento e \(1/5\) em reparo. A lei forte justifica essa interpretação temporal das probabilidades de equilíbrio neste modelo.
O Lema 6.5 implica que, para qualquer \(h\gt 0\), a cadeia amostrada nos instantes \(0,h,2h,\ldots \) tem matriz \(P_h\) irredutível. Ela também é aperiódica, pois \(P_h(i,i)\gt 0\). Se existe uma distribuição estacionária \(\pi \), o Teorema 3.10 fornece
Convergência para o equilíbrio Se uma cadeia de Markov em tempo contínuo \(X_t\) é não explosiva, irredutível e tem distribuição estacionária \(\pi \), então
Se \(nh\leq t\leq (n+1)h\), Chapman–Kolmogorov e a não negatividade das parcelas dão
Uma maneira de permanecer em \(j\) é não realizar nenhum salto durante o intervalo restante. Como esse intervalo tem duração no máximo \(h\),
Logo, \(P_t(i,j)\geq P_{nh}(i,j)e^{-\lambda _jh}\). Fixado \(h\gt 0\), o inteiro \(n=\lfloor t/h\rfloor \) cresce sem limite quando \(t\to \infty \). A convergência da cadeia amostrada fornece então \(\liminf _{t\to \infty }P_t(i,j)\geq \pi (j)e^{-\lambda _jh}\). Como isso vale para todo \(h\gt 0\), podemos fazer \(h\downarrow 0\), obtendo
Se \(A\) é um conjunto finito de estados que não contém \(j\), então
A primeira desigualdade usa \(P_t(i,j)\leq 1-\sum _{k\in A}P_t(i,k)\) e a finitude de \(A\); a segunda usa a cota inferior já obtida em cada estado \(k\). Escolhendo conjuntos finitos crescentes que esgotem \(S\setminus \{ j\} \), a soma das massas \(\pi (k)\) tende a \(1-\pi (j)\), pois \(\pi \) é uma distribuição de probabilidade. Assim, \(\limsup _{t\to \infty }P_t(i,j)\leq \pi (j)\). O limite inferior e o limite superior coincidem, provando a convergência.
Considere um modelo simplificado de tempo meteorológico com três estados: sol, nuvens e chuva. Depois de um período ensolarado, vem um período nublado; depois, chuva; e, por fim, o sol retorna. As permanências são exponenciais e independentes, com médias de \(3\), \(4\) e \(1\) dia, respectivamente.
Como a taxa de saída é o inverso do tempo médio de permanência, o gerador, na ordem sol, nuvens, chuva, é
Qual é a fração de tempo que o modelo passa em cada condição? Em equilíbrio, o fluxo que sai de um estado para o seguinte deve ser o mesmo nas três transições:
Juntando essas relações à normalização \(\pi (1)+\pi (2)+\pi (3)=1\), obtemos
Essas igualdades são precisamente as equações \(\pi Q=0\) com a condição de soma unitária. A interpretação também é simples: cada ciclo visita os três estados uma vez e dura, em média, \(3+4+1=8\) dias. O período nublado ocupa a maior fração do tempo porque sua permanência média é a mais longa, não porque o sistema passe por ele mais vezes.
6.4.1 Condição de balanço detalhado
Primeiro consideremos uma cadeia em um conjunto finito de estados \(F\subseteq S\). Conservamos as taxas de salto \(q(i,j)\) entre estados de \(F\) e suprimimos os demais saltos:
As equações de balanço detalhado ainda valem para essas taxas, com os pesos \(\pi (i)\), \(i\in F\); não precisamos normalizar os pesos nem supor que sejam positivos.
Escolha \(\Lambda _F\gt 0\) maior ou igual a todas as taxas de saída da cadeia restrita e uniformize:
Para \(i\ne j\), a igualdade \(\pi (i)U_F(i,j)=\pi (j)U_F(j,i)\) segue do balanço das taxas; para \(i=j\), é automática. Ao multiplicar essas igualdades ao longo de um caminho de \(n\) passos, vemos que um caminho de \(i\) a \(j\) e o mesmo caminho percorrido no sentido contrário satisfazem a mesma relação. Somando sobre todos os estados intermediários, obtemos, para todo \(n\ge 0\),
Pela fórmula de uniformização, a matriz de transição \(P_t^F\) é uma soma dessas potências, com pesos de Poisson que não dependem dos estados:
Portanto,
Passamos agora ao espaço de estados completo. Tomamos conjuntos finitos crescentes \(F_1\subseteq F_2\subseteq \cdots \) cuja união seja \(S\) (se \(S\) é finito, basta usar \(F=S\)). Para comparar as trajetórias, escolhemos \(\Lambda _m\gt 0\) com
A cota usa as taxas de saída da cadeia original, incluindo os destinos fora de \(F_m\). Enquanto as duas cadeias estão no mesmo estado \(x\in F_m\), usamos um relógio comum de taxa \(\Lambda _m\). Em cada toque, sorteamos o destino \(y\ne x\) com probabilidade \(q(x,y)/\Lambda _m\); com a probabilidade restante, conservamos \(x\).
Se o destino pertence a \(F_m\), ambas realizam o mesmo salto. Se fica fora de \(F_m\), a cadeia original sai e a restrita permanece em \(x\); a partir daí, não precisamos manter as trajetórias juntas. Na cadeia restrita, ignorar as tentativas para fora conserva exatamente as taxas \(q_{F_m}\) entre estados distintos e ajusta a diagonal à soma dessas taxas. É a construção por uniformização, agora com um mesmo relógio para comparar os dois processos.
As duas trajetórias assim construídas coincidem até a primeira saída da cadeia original de \(F_m\). Por isso, para \(i,j\in F_m\),
A não explosão garante que, até cada tempo fixo \(t\), há apenas um número finito de saltos quase certamente. Cada trajetória visita, portanto, apenas um conjunto finito de estados nesse intervalo e acaba contida em algum \(F_m\). Pela continuidade das probabilidades, a cota à direita tende a zero. Logo \(P_t^{F_m}(i,j)\to P_t(i,j)\).
Passando ao limite na identidade obtida para cada cadeia finita, concluímos
Somando em \(i\) e usando que a não explosão faz cada linha de \(P_t\) somar \(1\), obtemos
Assim, \(\pi \) é estacionária, como afirmado.
As equações de balanço detalhado costumam ser mais fáceis de resolver do que \(\pi Q=0\), mas são uma condição suficiente, não necessária. No Exemplo 6.15, por exemplo,
portanto a cadeia meteorológica não é reversível, embora tenha distribuição estacionária.
6.4.2 Cadeias de nascimento e morte
Uma cadeia de nascimento e morte só pode andar entre estados vizinhos. Quando está em \(n\), salta para \(n+1\) à taxa \(\lambda _n\) e, se \(n\gt 0\), para \(n-1\) à taxa \(\mu _n\). A estrutura linear do espaço de estados torna o balanço detalhado especialmente simples.
Os pesos são positivos pelas hipóteses sobre as taxas. Como \(Z=\sum _{n\in S}w_n\lt \infty \) e \(w_0=1\), a normalização \(\pi (n)=w_n/Z\) é não negativa e soma um. Na razão entre dois pesos consecutivos, todos os fatores comuns se cancelam:
Multiplicar por \(w_n\mu _{n+1}/Z\) dá, para todo \(n\) tal que \(n,n+1\in S\),
As demais taxas entre estados distintos são nulas, de modo que \(\pi \) satisfaz o balanço detalhado de (6.1). Essa igualdade diz que, em equilíbrio, o fluxo pela aresta \(n\leftrightarrow n+1\) é o mesmo nos dois sentidos. Pelo Teorema 6.8, \(\pi \) é estacionária; a hipótese de não explosão do enunciado é a exigida ali.
Retomemos a máquina do Exemplo 6.13, com taxas \(q(1,2)=\lambda \gt 0\) e \(q(2,1)=\mu \gt 0\). Já encontramos sua distribuição limite resolvendo as equações de Kolmogorov e a recuperamos por \(\pi Q=0\) no Exemplo 6.14. Agora a mesma distribuição aparece diretamente no balanço entre os únicos dois estados:
Portanto,
Recuperamos o mesmo equilíbrio sem calcular \(P_t\). O estado do qual se sai mais devagar recebe maior massa estacionária.
6.5 Distribuições e tempos de saída
As perguntas de saída em tempo contínuo são as mesmas de tempo discreto: por qual fronteira a cadeia escapa e quanto tempo isso leva? A cadeia de saltos decide o destino; os relógios exponenciais também entram no cálculo do tempo.
A diferença em relação ao tempo discreto é a unidade da espera: o tempo médio de retorno é medido em tempo físico, não pelo número de saltos. A cadeia de saltos tem as mesmas probabilidades de retorno, mas pode ter classificação diferente entre recorrência positiva e nula, pois as esperas dependem do estado. Um estado absorvente é tratado separadamente: como não há saída, o tempo \(T_k^+\) acima não se aplica.
Equação de Dirichlet para probabilidades de saída Sejam \(A\) e \(B\) conjuntos disjuntos, \(C=S\setminus (A\cup B)\) finito, e suponha que \(H_A\wedge H_B\lt \infty \) quase certamente quando a cadeia começa em \(C\). Então
é a única solução de
Se \(Q_C=(q(i,j))_{i,j\in C}\) e \(v(i)=\sum _{a\in A}q(i,a)\), a parte desconhecida de \(h\) satisfaz
A hipótese de saída implica \(\lambda _i\gt 0\) para \(i\in C\). Seja \(U_C=(r(i,j))_{i,j\in C}\) a restrição da matriz da cadeia de saltos. De cada estado de \(C\) existe um caminho de probabilidade positiva até a fronteira. Para cada estado inicial em \(C\), escolha um desses caminhos e multiplique suas probabilidades de transição; o produto é positivo. Como há um número finito de estados iniciais, o maior comprimento dos caminhos é algum \(m\lt \infty \), e o menor dos produtos é algum \(\varepsilon \gt 0\). Assim, a saída ocorre em até \(m\) saltos com probabilidade ao menos \(\varepsilon \), qualquer que seja a partida em \(C\). Se ainda não houve saída, a propriedade de Markov permite repetir a mesma estimativa no bloco seguinte de \(m\) saltos. Por indução,
onde a norma é a maior soma absoluta de uma linha. A soma de uma linha de \(U_C^n\) é a probabilidade de permanecer em \(C\) por \(n\) saltos. A cota geométrica implica a convergência de \(\sum _{n\geq 0}U_C^n\). Como \((I-U_C)\sum _{n=0}^NU_C^n=I-U_C^{N+1}\) e \(U_C^{N+1}\to 0\), concluímos que \((I-U_C)^{-1}=\sum _{n\geq 0}U_C^n\).
Condicionar no primeiro salto dá
Multiplicar por \(\lambda _i\) e usar \(q(i,i)=-\lambda _i\) produz \(Qh(i)=0\). Nas parcelas de \(Qh(i)\) que correspondem à fronteira, \(h\) vale um em \(A\) e zero em \(B\). Portanto,
ou seja, \(-Q_C h_C=v\). Se \(D\) é a matriz diagonal com entradas \(\lambda _i\), temos \(-Q_C=D(I-U_C)\). Os dois fatores são invertíveis: \(D\) tem diagonal estritamente positiva e a inversa de \(I-U_C\) foi construída acima. Assim, o sistema tem exatamente uma solução, a probabilidade de saída indicada.
Seja \(J\) o número de saltos até a saída. Pela construção em blocos da prova anterior, \(\mathbb P_i(J\gt km)\leq (1-\varepsilon )^k\). Consequentemente,
A hipótese de saída também garante \(\lambda _i\gt 0\) em \(C\). Como \(C\) é finito, \(a=\min _{i\in C}\lambda _i\gt 0\). Cada espera anterior à saída tem média no máximo \(1/a\), mas o número de esperas também é aleatório. Para somá-las, usamos a construção \(\tau _{n+1}=E_n/\lambda _{Y_n}\). No evento \(\{ J\gt n\} \), temos \(Y_n\in C\), de modo que
O evento \(\{ J\gt n\} \) depende apenas da cadeia de saltos e é independente de \(E_n\), cuja média é um. Somando os termos não negativos e tomando esperanças, obtemos
Condicionando no primeiro salto,
A primeira parcela é a duração média da espera inicial. A soma representa o tempo que ainda falta depois do salto; se o destino já está fora de \(C\), esse tempo é zero. Multiplicar por \(\lambda _i\) e reunir o termo \(-\lambda _i g(i)\) fornece \(Qg(i)=-1\). Como \(g=0\) fora de \(C\), a equação se escreve \(-Q_C g_C=\mathbf1\). A invertibilidade de \(-Q_C\), demonstrada acima, prova a unicidade e a fórmula \(g_C=(-Q_C)^{-1}\mathbf1\).
A mesma conta identifica cada entrada da matriz fundamental:
Essa interpretação também aparece diretamente na cadeia de saltos. Com \(D=\operatorname {diag}(\lambda _i)\) e \(U_C=(r(i,j))_{i,j\in C}\), já vimos que \(-Q_C=D(I-U_C)\); portanto,
A soma conta o número esperado de visitas da cadeia de saltos ao estado \(j\) antes da saída, incluindo a visita inicial. Cada visita a \(j\) dura, em média, \(1/\lambda _j\) unidades de tempo, o que explica a identidade de ocupação. Também podemos obtê-la pelas equações de primeiro salto: para \(j\) fixo, o vetor de tempos de ocupação satisfaz \(Qa=-\mathbf1_{\{ j\} }\) em \(C\), com valor zero na fronteira. Sua solução é a coluna \(j\) de \((-Q_C)^{-1}\). Somar as colunas recupera o tempo total esperado de saída.
Voltemos às duas máquinas do Exemplo 6.8. Nos estados \(A=(1,1)\), \(B=(1,0)\) e \(C=(0,1)\), o sistema ainda funciona. O estado \(F=(0,0)\) representa o desligamento definitivo. O reparador trabalha quando exatamente uma máquina está parada; depois de atingir \(F\), o sistema não volta a funcionar. Suponha agora taxas de falha \(\lambda _1=1\) e \(\lambda _2=2\) por dia e taxa de reparo \(\mu =3\) por dia.
Primeiro verificamos que o desligamento ocorre e tem média finita. De \(B\), a chance de a máquina restante falhar antes do reparo é \(1/(1+3)=1/4\); de \(C\), é \(2/(2+3)=2/5\). De \(A\), o primeiro salto leva a \(B\) ou a \(C\), e a probabilidade de o salto seguinte levar a \(F\) é ao menos \(1/4\). Portanto, de qualquer estado ainda operacional, há probabilidade ao menos \(1/4\) de desligamento nos próximos dois saltos. Se \(J\) conta os saltos até \(F\), o argumento de tentativas repetidas dá
As taxas de saída de \(A,B,C\) são \(3,4,5\) por dia; cada permanência antes do desligamento tem, assim, média no máximo \(1/3\) de dia. Somando as médias ao longo das visitas, como na prova do teorema anterior, concluímos que \(E_iH_{\{ F\} }\leq EJ/3\lt \infty \). As hipóteses da equação de Poisson para saída estão verificadas.
Escreva \(a=E_AH_{\{ F\} }\), \(b=E_BH_{\{ F\} }\) e \(c=E_CH_{\{ F\} }\). Em \(A\), as falhas das máquinas \(1\) e \(2\) competem: a espera média é \(1/3\) de dia; a falha da máquina \(2\) leva a \(B\) com probabilidade \(2/3\), e a falha da máquina \(1\) leva a \(C\) com probabilidade \(1/3\). Em \(B\) e \(C\), competem o reparo e a falha da máquina que ainda funciona. Logo,
Nos dois últimos casos, o salto para \(F\) não acrescenta tempo futuro, pois o tempo de chegada a \(F\) já foi encerrado. Substituindo essas duas expressões na primeira, obtemos
Portanto \(3a/10=17/30\), e
em dias. Quando apenas uma máquina funciona, importa qual é ela: \(b\gt c\) porque em \(B\) permanece a máquina de menor taxa de falha. O número de máquinas em funcionamento seria o mesmo nos dois estados, mas o tempo que ainda resta não tem a mesma distribuição.
6.6 Filas markovianas
Uma fila é markoviana quando o estado atual contém tudo de que precisamos para descrever seu futuro. Com chegadas de Poisson e serviços exponenciais, a falta de memória permite usar apenas o número de clientes no sistema: não precisamos guardar há quanto tempo o cliente em serviço está sendo atendido.
Escreva \(\rho =\lambda /\mu \). A forma produto das cadeias de nascimento e morte dá pesos \(w_n=\rho ^n\). Eles podem ser normalizados somente se \(\rho \lt 1\), isto é, se a capacidade média de serviço excede a taxa de chegada.
A taxa total de saída é limitada por \(\lambda +\mu \), portanto não há explosão. A equação de equilíbrio em zero é \(\pi (0)\lambda =\pi (1)\mu \); para \(n\geq 1\), temos
A primeira igualdade equilibra o fluxo entre \(0\) e \(1\). Substituindo-a na equação de \(n=1\), obtemos o mesmo equilíbrio entre \(1\) e \(2\); repetindo o argumento, chegamos a
Se \(\rho \lt 1\), a soma da série geométrica determina \(\pi (0)=1-\rho \). Esses pesos satisfazem o balanço detalhado, que garante a estacionariedade, e a irredutibilidade garante sua unicidade. Além disso,
Para justificar a soma que calcula \(L\) sem derivar uma série, escreva \(n=\sum _{k=1}^n1\) e reagrupe os termos não negativos:
Multiplicar por \(1-\rho \) dá o valor anunciado de \(L\). Se \(\rho \geq 1\) e \(\pi (0)\gt 0\), a série \(\pi (0)\sum _{n\geq 0}\rho ^n\) diverge; se \(\pi (0)=0\), a recursão força \(\pi (n)=0\) em todos os estados. Nenhum caso produz uma distribuição de probabilidade, provando a inexistência afirmada.
A última afirmação é uma aplicação da propriedade PASTA (Poisson arrivals see time averages): quando as tentativas de chegada são Poisson e não antecipam o estado da fila, as proporções observadas pelas chegadas coincidem com as proporções de tempo. A taxa de tentativas permanece \(\lambda \) mesmo quando a capacidade está esgotada.
A propriedade pode ser entendida primeiro por um cálculo em médias. Considere o sistema iniciado em equilíbrio e divida \((0,t]\) em pequenos intervalos de duração \(h\). Se a fila está cheia no início de um deles, a probabilidade de uma tentativa de chegada nesse intervalo é \(\lambda h+o(h)\). O erro ao usar apenas o estado inicial é da ordem de \(h^2\): para produzir uma diferença, precisam ocorrer tanto uma mudança de estado quanto uma tentativa de chegada nesse mesmo intervalo. As taxas são limitadas porque a capacidade é finita. Somando os intervalos e fazendo \(h\downarrow 0\), obtemos
onde \(R(t)\) conta as recusas e \(A(t)\) todas as tentativas. A razão dessas esperanças é \(\pi (K)\). A afirmação mais forte, de convergência quase certa da fração observada \(R(t)/A(t)\), será demonstrada na Seção 6.10, usando apenas ciclos independentes e a lei dos grandes números. Uma referência para a formulação geral é Wolff (1982).
Chegadas que dependam do estado da fila não satisfazem, em geral, as hipóteses de PASTA.
6.6.1 Vários servidores
Na fila \(M/M/s\) do Exemplo 6.6, há \(s\) servidores, cada um com taxa de serviço \(\mu \). Se existem \(n\lt s\) clientes, somente \(n\) servidores estão ocupados e a taxa total de saída é \(n\mu \). Se \(n\geq s\), todos trabalham e a taxa total é \(s\mu \). Assim,
Escreva \(a=\lambda /\mu \). Pela forma produto, a razão entre pesos consecutivos é
Enquanto \(n\lt s\), cada nova razão é \(a/(n+1)\). Depois que todos os servidores estão ocupados, as razões são constantes, iguais a \(a/s\). Começando com \(w_0=1\), obtemos
A cauda é geométrica com razão \(\lambda /(s\mu )\). Portanto, a condição de estabilidade é
e, sob essa condição, \(\pi (n)=w_n/\sum _{k\geq 0}w_k\). A desigualdade apenas diz que, a longo prazo, a demanda média deve ser menor que a capacidade total dos servidores.
6.7 Distribuições explícitas em modelos enumeráveis
Os modelos de população e de atendimento também permitem acompanhar a distribuição em um instante fixo. Nos dois casos seguintes, a independência dos mecanismos transforma uma cadeia com infinitos estados em contas com distribuições conhecidas.
6.7.1 Yule: nascer em tempos diferentes
Retomemos o processo de Yule: cada indivíduo produz um novo indivíduo à taxa \(a\gt 0\), independentemente dos demais, e não há mortes. Se há \(n\) indivíduos, os \(n\) relógios competem e a população passa de \(n\) a \(n+1\) à taxa \(an\). A não explosão já foi provada no Exemplo 6.10, no caso em que a potência é um. Podemos, portanto, contar a população em todo instante finito.
Escreva \(p_n(t)=\mathbb P_1(Z_t=n)\). Para ficar no estado 1 até \(t\), o primeiro relógio não pode ter tocado; logo, \(p_1(t)=e^{-at}\). Para os demais estados, usaremos as esperas já presentes na construção, em vez de derivar uma soma infinita.
Seja \(H_n\) o primeiro instante em que a população atinge \(n\), com \(H_1=0\). O tempo \(W_n=H_{n+1}-H_n\) é exponencial de taxa \(an\), e essas esperas são independentes. Para cada \(n\geq 2\), \(H_n\) é uma soma finita de exponenciais independentes e tem uma densidade \(g_n\). Como \(H_2=W_1\), temos \(g_2(s)=ae^{-as}=ap_1(s)\). Para \(n\geq 3\), a convolução de \(H_{n-1}\) com \(W_{n-1}\) dá
Por outro lado, estar no estado \(n-1\) em \(s\) significa ter chegado a ele em algum \(u\leq s\) e não ter saído até \(s\). A independência da nova espera fornece
Comparar as duas integrais mostra que \(g_n(s)=(n-1)ap_{n-1}(s)\), também válido para \(n=2\). Para estar em \(n\) no instante \(t\), precisamos chegar em algum \(s\leq t\) e permanecer ali até \(t\). Portanto,
Esse argumento usa somente somas e integrais de um número finito de esperas para cada \(n\) fixado.
Façamos indução em \(n\). Já provamos o caso \(n=1\). Substituir a fórmula do caso \(n-1\) na última integral dá
Na terceira linha, fizemos \(v=e^{as}-1\), de modo que \(dv=ae^{as}\, ds\), e integramos \(v^{n-2}\). Isso completa a indução. Para \(t\gt 0\), ponha \(p=e^{-at}\) e \(r=1-p\), com \(0\lt r\lt 1\). As massas obtidas somam \(p\sum _{n\geq 1}r^{n-1}=1\). Além disso,
Pela fórmula da cauda para variáveis inteiras não negativas (Lema 2.13),
Não foi preciso trocar uma derivada com uma série. Em \(t=0\), o valor é \(Z_0=1\), e a fórmula da média continua válida.
Com \(k\) indivíduos iniciais, separe as famílias descendentes de cada um. Os relógios são independentes entre famílias; cada família segue uma cópia do processo iniciado em um indivíduo. A soma dessas \(k\) populações tem taxa total de nascimento \(an\) quando o total é \(n\), reproduzindo a construção do processo iniciado em \(k\). A linearidade de uma soma finita de esperanças dá \(E_kZ_t=ke^{at}\).
6.7.2 Atendimento imediato e a fila \(M/M/\infty \)
Imagine um serviço em que cada chegada inicia seu atendimento imediatamente. Pode representar um conjunto de tarefas executadas em paralelo quando não há uma restrição relevante de vagas. A expressão “infinitos servidores” especifica essa regra matemática: não há espera por um atendente. O estado ainda conta quantos clientes estão no sistema.
Suponha chegadas de Poisson de taxa \(\lambda \gt 0\) e serviços exponenciais independentes de taxa \(\mu \gt 0\), também independentes das chegadas. Quando há \(n\) clientes, os \(n\) serviços em curso competem; portanto,
A taxa de saída é ilimitada quando \(n\) cresce, mas isso não produz explosão. Até um instante \(t\), o número \(A(t)\) de chegadas é finito quase certamente. Começando com \(n_0\lt \infty \) clientes, o número de conclusões de serviço não pode exceder \(n_0+A(t)\). Logo, o número total de mudanças até \(t\) é no máximo \(n_0+2A(t)\) e também é finito.
Podemos descobrir a distribuição de \(X_t\) separando duas origens dos clientes presentes: os que já estavam no sistema no instante zero e os que chegaram depois. Fixe \(t\gt 0\) e escreva
Cada cliente inicial permanece até \(t\) com probabilidade \(p\), independentemente dos demais. O número \(B_t\) de sobreviventes iniciais tem, portanto, distribuição \(\operatorname {Binomial}(n_0,p)\).
Para contar os clientes que chegaram depois de zero, condicione no total \(A(t)=m\). Pelo Teorema 5.15, os instantes das chegadas são uniformes no intervalo, colocados em ordem. Como queremos apenas um total de sobreviventes, podemos primeiro usar \(m\) uniformes independentes, atribuir serviços independentes a esses clientes e depois ordenar os instantes; a ordenação não altera o total. Um cliente que chega em \(s\) ainda está presente em \(t\) com probabilidade \(e^{-\mu (t-s)}\). A probabilidade média, para uma chegada uniforme em \([0,t]\), é
Os pares formados pelo instante uniforme e pelo serviço são independentes entre clientes. Assim, condicionado a \(A(t)=m\), o número \(C_t\) desses clientes ainda presentes é binomial com parâmetros \(m\) e \(\bar p_t\). Afinar a contagem de Poisson de média \(\lambda t\) dá
Os serviços dos clientes iniciais são independentes das novas chegadas e de seus serviços; logo, \(B_t\) e \(C_t\) são independentes. Obtivemos a descrição completa
Em particular,
O primeiro termo mede o que resta da população inicial. O segundo mede os clientes recebidos desde o início que ainda estão em serviço.
Agora podemos verificar o equilíbrio de duas maneiras. As taxas \(\lambda \gt 0\) e \(n\mu \gt 0\) permitem percorrer qualquer trecho finito de estados vizinhos; portanto, a cadeia é irredutível. Os pesos de nascimento e morte são \(w_n=a^n/n!\), e sua soma é \(e^a\). Pelo Teorema 6.9,
é estacionária. Também podemos começar com um número inicial \(X_0\sim \operatorname {Poisson}(a)\), independente de todos os relógios futuros. O afinamento dos clientes iniciais dá \(B_t\sim \operatorname {Poisson}(ap)\); os novos sobreviventes têm lei \(\operatorname {Poisson}(a(1-p))\), independentemente de \(B_t\). A soma volta a ser \(\operatorname {Poisson}(a)\) para todo \(t\).
Partindo de um \(n_0\) fixado, essa distribuição também é o limite. Para cada \(k\geq 0\), a independência dá a soma finita
Quando \(t\to \infty \), \(p\to 0\), de modo que a parcela \(j=0\) tende a \(e^{-a}a^k/k!\) e as demais tendem a zero. Isso prova a convergência sem trocar uma soma infinita com um limite. A estacionária é única: se outra estacionária \(\nu \) existisse, escolheríamos primeiro um conjunto finito de estados iniciais com massa de \(\nu \) maior que \(1-\varepsilon \). Nesse conjunto a convergência pode passar pela soma finita. Mais explicitamente, para esse conjunto \(F\),
A soma finita tende a zero. Como \(\varepsilon \) é arbitrariamente pequeno, a identidade \(\nu P_t=\nu \) dá \(\nu (k)=\pi (k)\) para todo \(k\).
Por fim, o número médio em equilíbrio é \(a=\lambda /\mu \), pois
Ao contrário de uma fila com um número fixo de atendentes, o modelo não impõe um limite à taxa total de serviço: ela cresce com o número de clientes presentes. Por isso há equilíbrio para quaisquer taxas positivas de chegada e de serviço.
6.8 Exercícios
Os primeiros problemas trabalham relógios, geradores, probabilidades e equilíbrio. Em seguida, os modelos da oficina e das populações pedem escolher o estado e explicar o efeito de uma mudança nas hipóteses. As taxas devem usar unidades compatíveis; toda conclusão deve ser acompanhada da propriedade que a justifica.
6.8.1 Relógios, taxas e equilíbrio
6.8.2 Modelagem e variações dos exemplos
Os problemas seguintes retomam os modelos descritivos da abertura. Antes de calcular, explique por que os estados escolhidos conservam a informação necessária e indique a unidade de cada taxa.
6.9 Redes de filas*
Uma requisição pode passar por autenticação, consultar um banco de dados e executar um processamento antes de sair. Se parte delas retorna a uma etapa anterior, quantas visitas cada servidor recebe por requisição externa? Essa contabilidade vem antes de qualquer cálculo de congestionamento.
A matriz \(R\) é subestocástica: a massa que falta em cada linha representa a saída da rede. Aqui \(R\) roteia clientes entre estações; não é a matriz da cadeia de saltos do vetor de comprimentos das filas. Suponha que, de toda estação, exista um caminho de roteamento com probabilidade positiva até a saída. Como \(K\) é finito, há um número de serviços e uma probabilidade positiva uniformes para sair: tentativas repetidas mostram que \(R^n\to 0\) com uma cota geométrica. Assim,
existe. Equivalentemente, o raio espectral de \(R\) é menor que \(1\).
As taxas efetivas de chegada \(\gamma _i\) contam todas as visitas, inclusive retornos. A conservação do fluxo requer as equações de tráfego
com vetores-linha. Portanto,
O termo \(\lambda R^n\) conta visitas depois de \(n\) encaminhamentos. A fórmula calcula a demanda média que cada estação deverá sustentar; não afirma, por si só, que a rede suporte essa demanda.
A forma produto foi estabelecida por Jackson (1957); Kelly (1979) desenvolve suas relações com redes estocásticas. A prova a seguir explicita o balanço global. Ao contrário do caso de uma única fila de nascimento e morte, os fluxos não precisam se compensar par a par.
Primeiro passo: construção e acessibilidade. Escreva \(n=(n_1,\ldots ,n_K)\) e denote por \(e_i\) o vetor unitário da estação \(i\). As transições possíveis são
Se mais de um mecanismo leva ao mesmo destino, somamos suas taxas. A taxa total é limitada por \(\sum _i\lambda _i+\sum _i\mu _i\). A uniformização fornece, portanto, uma construção não explosiva.
De todo vetor \(n\) é possível chegar ao vetor vazio: escolhemos um cliente e o encaminhamos por um caminho de roteamento até a saída, repetindo o procedimento para os demais. Cada passo desse caminho tem taxa positiva, e podemos exigir a ausência de chegadas externas e das outras conclusões de serviço durante essa sequência finita. Reciprocamente, a hipótese de acessibilidade a partir de uma chegada externa permite acrescentar um cliente a qualquer estação escolhida. Basta realizar uma chegada numa estação de taxa externa positiva e conduzi-la por um caminho até a estação desejada, sem realizar outros eventos. Nos estados intermediários, o incremento e o decremento do número de clientes se compensam; apenas a estação de destino ganha uma unidade. Repetir essas operações constrói qualquer vetor de comprimentos de fila. Toda sequência finita de eventos assim prescrita tem probabilidade positiva. Logo, a cadeia é irredutível.
Como de alguma chegada externa se alcança cada estação, a série \(\gamma =\sum _{m\geq 0}\lambda R^m\) também mostra que \(\gamma _i\gt 0\) para todo \(i\). Sob a hipótese \(\gamma _i\lt \mu _i\), temos então \(0\lt \rho _i\lt 1\).
Segundo passo: normalização e balanço. A candidata do enunciado é positiva e soma um, pois há apenas \(K\) coordenadas e cada fator é a massa de uma distribuição geométrica:
Fixe um vetor \(n\). Podemos entrar nele por uma chegada externa a partir de \(n-e_j\), por uma saída da rede a partir de \(n+e_i\) ou por uma transferência de \(i\) para \(j\) a partir de \(n+e_i-e_j\). Nos casos que exigem \(n_j\gt 0\), essa condição exclui coordenadas negativas. As razões das massas são
Assim, o fluxo total de entrada, dividido por \(\pi (n)\), é
Como \(\mu _i\rho _i=\gamma _i\), agrupamos os termos que contêm a mesma indicadora e aplicamos as equações de tráfego:
Somar as mesmas equações em \(j\) dá
Portanto, o fluxo de entrada dividido por \(\pi (n)\) se reduz a
que é exatamente a taxa total de saída de \(n\). Isso prova \(\pi Q=0\). Como as taxas são limitadas, o Lema 6.6 garante que \(\pi \) é estacionária.
Terceiro passo: recorrência e médias. Escolha na uniformização uma taxa estritamente maior que a cota das taxas de saída. A cadeia discreta uniformizada é irredutível e tem a mesma estacionária \(\pi \). Pelo resultado dos capítulos anteriores para cadeias enumeráveis, ela é positivamente recorrente e sua estacionária é única. Para passar à noção de retorno em tempo contínuo, fixemos um estado \(a\). A espera até a saída real de \(a\) tem média finita, e há apenas um número finito de destinos possíveis para esse salto, pois o número de estações é finito. De cada destino \(b\ne a\), a cadeia uniformizada atinge \(a\) em um número médio finito de passos, pela recorrência positiva discreta. Cada passo consome uma espera independente de média igual ao inverso da taxa de uniformização. O tempo físico médio até atingir \(a\) a partir de \(b\) é, portanto, finito. Somar a espera inicial e a média sobre os finitos destinos prova que o retorno depois de uma saída real também tem média finita. A cadeia em tempo contínuo é, assim, positivamente recorrente. Qualquer outra estacionária em tempo contínuo satisfaria \(\nu Q=0\) e, portanto, seria estacionária para a mesma matriz uniformizada; logo, coincidiria com \(\pi \). A fatoração de \(\pi \) prova a independência dos comprimentos num instante em equilíbrio. A média geométrica já calculada para a fila \(M/M/1\) fornece \(E_\pi X^i=\rho _i/(1-\rho _i)\).
Quarto passo: necessidade da condição de carga. Suponha agora que exista alguma distribuição estacionária \(\nu \), sem admitir de antemão a forma produto. Defina a taxa média de serviços concluídos na estação \(i\) por
Vamos justificar a conservação dessas taxas sem supor finita a média do comprimento das filas. Para cada inteiro \(M\geq 1\), use a função limitada \(f_M(n)=\min (n_j,M)\). A estacionariedade e a expansão uniforme \(P_h=I+hQ+O(h^2)\) dão \(E_\nu (Qf_M)=0\). Quando \(n_j\lt M\), uma chegada externa ou uma transferência para \(j\) aumenta \(f_M\) em um. Quando \(1\leq n_j\leq M\), uma conclusão de serviço em \(j\) a reduz em um: usamos aqui \(R_{jj}=0\), pois o cliente sai da rede ou segue para outra estação. A taxa total dessas reduções é, portanto, \(\mu _j\). Assim,
Ao fazer \(M\to \infty \), cada probabilidade converge pela continuidade em sequências crescentes de eventos. As somas têm apenas \(K\) termos e as taxas são finitas; obtemos
A abertura do roteamento garante que \(I-R\) é invertível, logo a única solução dessas equações é \(d=\gamma \).
Finalmente, a irredutibilidade implica que qualquer estacionária atribui massa positiva a todo estado. De fato, se \(\nu (a)\gt 0\), a positividade de \(P_t(a,b)\) e a identidade \(\nu P_t=\nu \) dão \(\nu (b)\gt 0\). Em particular, o vetor vazio tem massa positiva e \(\mathbb P_\nu (X^j=0)\gt 0\). Portanto,
Se alguma \(\gamma _j\geq \mu _j\), chegamos a uma contradição. Isso prova a inexistência de uma distribuição estacionária nesse caso.
O caso de duas estações em série permite conferir o balanço geral com apenas três mecanismos de entrada.
Chegadas externas de taxa \(\lambda \gt 0\) ocorrem apenas na estação 1; toda saída de 1 entra em 2 e toda saída de 2 deixa a rede. Então \(\gamma =(\lambda ,\lambda )\). Suponha \(\lambda \lt \min (\mu _1,\mu _2)\) e ponha \(\rho _i=\lambda /\mu _i\). A candidata \(\pi (m,n)=(1-\rho _1)(1-\rho _2)\rho _1^m\rho _2^n\) soma 1.
Há três formas de entrar em \((m,n)\): uma chegada a partir de \((m-1,n)\), um serviço em 1 a partir de \((m+1,n-1)\) e um serviço em 2 a partir de \((m,n+1)\). Dividindo o fluxo de entrada por \(\pi (m,n)\), obtemos
Esse é exatamente o fluxo de saída dividido por \(\pi (m,n)\). As indicadoras tratam também as bordas \(m=0\) e \(n=0\), sem recorrer a estados negativos. Logo \(\pi Q=0\); como as taxas são limitadas, isso garante estacionariedade.
A forma produto descreve uma fotografia em equilíbrio. Não torna independentes as trajetórias das filas: a saída de uma alimenta a outra. Também não implica balanço detalhado, pois a transferência \((m,n)\to (m-1,n+1)\) da rede em série não possui uma transferência direta inversa.
Retomemos a API da abertura, com o roteamento da Figura 6.6. As estações são \(1=\) entrada da API, \(2=\) autenticação, \(3=\) banco de dados e \(4=\) processamento. As taxas, medidas por segundo, e as probabilidades de roteamento são
Por exemplo, metade das requisições que terminam a entrada segue para autenticação, e \(20\% \) das que terminam o processamento voltam à autenticação. A probabilidade de saída é o que falta para completar cada linha.
As equações são
Substituindo a terceira na quarta, resulta \(\gamma _4=2{,}5+0{,}5\gamma _2\). Logo \(0{,}9\gamma _2=5{,}5\) e
A rede é estável, mas o banco de dados é o gargalo: sua utilização é \(71/81\approx 0{,}877\), e o número médio de clientes nessa estação, incluindo o que está em serviço, é
Se a entrada externa crescer \(20\% \) com o mesmo roteamento, todas as taxas \(\gamma _i\) crescem \(20\% \). O banco passa a receber \(142/15\gt 9\) visitas por segundo: a rede perde estabilidade embora a estação de entrada ainda tenha capacidade disponível.
Para confrontar a rede com dados reais, é importante distinguir o tempo de espera do tempo de serviço. Um registro útil identifica cada requisição e os instantes em que ela chega, começa a ser atendida e termina o atendimento em cada estação. Com esses dados, a taxa externa \(\lambda _i\) pode ser estimada dividindo as chegadas pelo tempo de observação, e \(R_{ij}\) pela proporção de serviços que encaminham o cliente de \(i\) para \(j\). As saídas da rede também precisam ser contabilizadas. Já \(\mu _i\) é estimada por serviços concluídos divididos pelo tempo em que o servidor esteve ocupado: incluir o tempo de espera nesse denominador confundiria congestionamento com velocidade de serviço.
O passo seguinte é comparar a ocupação e os comprimentos de fila previstos com os registros de um período posterior, verificando também se as durações dos serviços se aproximam da lei exponencial. Um cache pode evitar etapas inteiras; o processamento em lotes, as prioridades e os limites de conexão podem mudar a dinâmica de atendimento. Tempos de serviço muito variáveis também enfraquecem a hipótese exponencial. A forma produto é um resultado exato para o modelo especificado, mas sua aplicação a uma arquitetura real depende de essas escolhas representarem adequadamente o sistema.
6.10 PASTA: demonstração por ciclos*
Retomemos a fila com capacidade \(K\ge 1\), tentativas de chegada Poisson de taxa \(\lambda \gt 0\) e um servidor exponencial de taxa \(\mu \gt 0\). Vamos justificar por que a fração de tentativas recusadas tende a \(\pi (K)\) quase certamente. O argumento emprega apenas a construção por relógios e a lei forte dos grandes números para variáveis independentes.
Comece com o sistema vazio. Um ciclo começa em uma visita ao estado \(0\) e termina na próxima volta a \(0\) depois de pelo menos uma chegada. Ao retornar a \(0\), todos os relógios relevantes recomeçam, pela falta de memória e pelas independências do modelo. As durações dos ciclos, as contagens de tentativas e as contagens de recusas formam, portanto, sequências de variáveis aleatórias i.i.d. por ciclos.
Cada ciclo tem duração média finita. De qualquer estado ocupado, existe probabilidade positiva, limitada abaixo uniformemente nos \(K\) estados ocupados, de chegar a \(0\) em no máximo \(K\) mudanças: basta que ocorram serviços sucessivos sem novas chegadas aceitas. Repetindo tentativas em blocos de \(K\) mudanças, obtemos uma cauda geométrica para o número de mudanças até esvaziar a fila. Cada espera entre mudanças tem média no máximo \(1/\min \{ \lambda ,\mu \} \); logo, o tempo médio do ciclo é finito.
Dentro de um ciclo, denote por \(D\) sua duração, por \(O_i\) o tempo total no estado \(i\), por \(V_i\) o número de permanências nesse estado, por \(A\) o total de tentativas de chegada e por \(R\) o total de recusas. As taxas de mudança real de estado são
Em cada visita a \(i\), a permanência tem média \(1/\delta _i\); a escolha do destino é independente dessa espera. Há um cuidado ao somar essas contribuições: o número de visitas é aleatório. Para cada \(r\geq 1\), o evento de ocorrer uma \(r\)-ésima visita já está decidido antes dos sorteios dessa visita. Sua contribuição esperada é, portanto, \(\mathbb P(V_i\geq r)/\delta _i\). Somando em \(r\), obtemos
Da mesma forma, o número esperado de transições reais de \(i\) para \(j\) durante o ciclo é
O ciclo começa e termina em \(0\), de modo que, para cada estado \(j\), as entradas e saídas ocorrem no mesmo número. Tomando esperanças,
Logo, os pesos \(w_i=E O_i\) satisfazem \(wQ=0\). Ao normalizá-los pela soma \(E D\), obtemos uma distribuição estacionária. Como a fila finita é irredutível, essa distribuição é a única estacionária \(\pi \). Portanto,
Agora contemos as tentativas de chegada segundo o estado encontrado imediatamente antes de cada tentativa. Os mecanismos são diferentes no interior da fila e quando ela está cheia.
Se \(i\lt K\), uma chegada é aceita e encerra a permanência em \(i\). A visita contribui com uma tentativa se termina por chegada e com zero se termina por serviço. Essa contagem é Bernoulli de parâmetro \(\lambda /\delta _i\), incluindo o caso \(i=0\), em que o parâmetro é um.
Em \(i=K\), uma tentativa é recusada e não produz salto da cadeia. A mesma permanência pode, portanto, conter várias recusas. Sua duração \(S\) é exponencial de taxa \(\mu \), independente das tentativas de chegada. Condicionada a \(S=s\), a contagem de recusas tem lei \(\operatorname {Poisson}(\lambda s)\), com média \(\lambda s\). Sem condicionar na duração, ela é geométrica em \(\mathbb N_0\): contamos chegadas antes do primeiro serviço, pelo mesmo argumento do Exemplo 5.9. Em particular, sua média é
Assim, embora as contagens por visita tenham leis diferentes, sua média é \(\lambda /\delta _i\) nos dois casos. Somando por visitas, com a mesma justificativa usada para os tempos de ocupação, obtemos
Assim,
Para os primeiros \(m\) ciclos completos, a lei forte dos grandes números dá
O número de ciclos completos até o instante \(t\) tende a infinito quando \(t\to \infty \), pois os ciclos têm duração média finita e positiva. Se \(m\) ciclos terminaram até \(t\), as contagens crescentes de tentativas e recusas permitem limitar a razão \(R(t)/A(t)\) entre
Ambos os extremos têm o mesmo limite \(\pi (K)\). Isso estende a convergência a todo \(t\to \infty \). Se a fila começa ocupada, basta descartar o trecho inicial até sua primeira visita a \(0\), que é finito quase certamente.
6.11 Modelo de Jukes–Cantor*
A uniformização também aparece em modelos de evolução molecular. Neste exemplo, um mesmo sítio pode sofrer várias substituições, e a base observada no final não informa diretamente quantas mudanças ocorreram.
Considere os quatro nucleotídeos \(A,C,G,T\). No modelo de Jukes–Cantor, cada base muda para cada uma das outras três à mesma taxa \(\mu \gt 0\) por unidade de tempo. Assim, o gerador tem entradas \(\mu \) fora da diagonal e \(-3\mu \) na diagonal.
Podemos uniformizar a cadeia com um relógio de taxa \(4\mu \): quando ele toca, escolhemos uniformemente uma das quatro bases, permitindo que a base sorteada seja a atual. Depois do primeiro toque, o estado é uniforme. Portanto,
Em particular, a probabilidade de a base observada ser diferente da inicial é
Se \(v=3\mu t\) é o número esperado de substituições reais por sítio, então, para \(0\leq f\lt 3/4\),
O logaritmo corrige o fato de que várias substituições no mesmo sítio podem esconder umas às outras: observar uma diferença não é o mesmo que contar todas as mudanças ocorridas.
6.12 Ramificação e imigração*
Uma população pode crescer por reprodução dos indivíduos presentes ou pela chegada de indivíduos de fora. Essa distinção altera o significado de encontrar a população vazia. Sem imigração, zero é absorvente; com imigração, novas chegadas podem repovoar o sistema. Estudaremos primeiro a reprodução e a morte e, depois, acrescentaremos a entrada externa.
6.12.1 Famílias que evoluem em seus próprios relógios
Retomemos o modelo do Exemplo 6.7. Cada indivíduo produz um novo indivíduo à taxa \(\lambda \gt 0\) e morre à taxa \(\mu \gt 0\), independentemente dos demais. Se \(Z_t\) é o tamanho da população, suas taxas são
e zero é absorvente. Um nascimento aumenta o total em um, enquanto uma morte o diminui em um. Os tempos entre mudanças dependem do tamanho atual: com \(n\) indivíduos, há \(n\) pares de relógios competindo.
Há uma descrição equivalente que deixa a árvore de descendência mais visível. Ponha \(a=\lambda +\mu \). Cada indivíduo vive até tocar um relógio exponencial de taxa \(a\). Nesse instante, é substituído por dois indivíduos com probabilidade \(\lambda /a\) ou por nenhum com probabilidade \(\mu /a\). A corrida de exponenciais justifica as probabilidades. Na primeira opção, substituir um por dois produz o mesmo aumento de uma unidade que um nascimento; na segunda, retirar o indivíduo produz a morte. Depois de uma substituição por dois, as duas famílias usam sorteios independentes e obedecem à mesma regra original.
Precisamos primeiro saber que essa construção não acumula infinitos eventos em tempo finito. Podemos construí-la dentro de uma árvore maior: nela, todo indivíduo vive um tempo exponencial de taxa \(a\) e é sempre substituído por dois. Essa população maior é um processo de Yule de taxa \(a\). Marcamos inicialmente seu indivíduo. Quando um indivíduo marcado se divide, marcamos os dois filhos se o sorteio do modelo original indica nascimento; se indica morte, não marcamos nenhum. Filhos de indivíduos não marcados continuam sem marca. O número de indivíduos marcados tem as taxas de \(Z\). Como o processo de Yule é não explosivo, pelo Exemplo 6.10, há apenas finitas divisões da árvore maior em cada intervalo limitado. O mesmo vale para os eventos da população marcada.
Essa construção fornece também duas estimativas que usaremos nas provas. Se \(Y\) é a população maior, iniciada em um indivíduo, então
pela Proposição 6.13. Além disso, cada mudança de \(Z\) corresponde a uma divisão de \(Y\). Para \(h\geq 0\),
A desigualdade conta eventos: cada mudança do total marcado tem módulo um, e cada divisão da árvore maior aumenta seu total em um. Tomando esperanças,
Em particular, a média de \(Z_t\) é finita e depende continuamente de \(t\).
Começando com \(k\) indivíduos, podemos acompanhar \(k\) famílias independentes, cada uma iniciada por um indivíduo. Seus tamanhos somam \(Z_t\). A geradora de uma soma de variáveis independentes é o produto de suas geradoras; portanto, o produto tem \(k\) fatores iguais a \(F(t,s)\).
Agora começamos com um indivíduo e condicionamos no instante \(U\) de seu primeiro evento. Se \(U\gt t\), ainda há um indivíduo em \(t\), contribuindo com \(s\). Se o primeiro evento ocorre em \(u\leq t\), há duas possibilidades. A morte deixa população zero, contribuindo com \(1\) à geradora. Um nascimento deixa duas famílias independentes, que evoluem durante \(t-u\) e contribuem com \(F(t-u,s)^2\). A densidade de \(U\) é \(ae^{-au}\); multiplicá-la pelas probabilidades \(\mu /a\) e \(\lambda /a\) dá
Todos os valores de \(F\) estão entre zero e um. Também há continuidade em \(t\): se não ocorre evento entre \(t\) e \(t+h\), os valores de \(s^{Z}\) são iguais; em qualquer trajetória sua diferença tem módulo no máximo um. Assim,
e a última expressão tende a zero. A mesma estimativa, aplicada de \(t-h\) a \(t\), fornece continuidade à esquerda.
Na integral, faça \(v=t-u\) e multiplique a identidade por \(e^{at}\):
O integrando agora é uma função contínua. Pelo teorema fundamental do cálculo, a derivada do lado direito é \(e^{at}[\mu +\lambda F(t,s)^2]\). A regra do produto no lado esquerdo fornece
que é a equação anunciada. Em \(t=0\), temos \(Z_0=1\) e \(F(0,s)=s\).
A equação tem solução única entre as funções com valores em \([0,1]\) e com a condição inicial dada. Para conferir isso diretamente, sejam \(F\) e \(G\) duas soluções, com \(s\) fixado, e ponha \(d(t)=F(t,s)-G(t,s)\). Subtrair as equações dá
Multiplicar pelo fator
produz uma função de derivada zero e valor inicial zero. Logo \(d(t)=0\). Essa verificação permite reconhecer uma solução calculada por separação de variáveis ou conferir uma fórmula candidata.
Para a média, começamos com um indivíduo e escrevemos \(m(t)=E_1 Z_t\). Ela é finita e contínua pelas estimativas da árvore maior. Condicionar no primeiro evento, como na prova anterior, dá uma contribuição um se esse evento ainda não ocorreu, zero se ele é uma morte e duas médias \(m(t-u)\) se ele é um nascimento. Portanto,
Substituindo \(v=t-u\) e multiplicando por \(e^{at}\),
Podemos derivar essa integral porque seu integrando é contínuo. Obtemos \(m'(t)=(2\lambda -a)m(t)=(\lambda -\mu )m(t)\) e \(m(0)=1\). A solução é \(m(t)=e^{(\lambda -\mu )t}\). As \(k\) famílias independentes somam suas médias, dando a fórmula geral.
Para a extinção, olhemos para a árvore de descendência, esquecendo por um momento os comprimentos das vidas. Cada indivíduo tem zero filhos com probabilidade \(\mu /a\) e dois com probabilidade \(\lambda /a\). É uma árvore de Galton–Watson com geradora
O evento de extinção dessa árvore é o mesmo que o de extinção em tempo contínuo. Se a árvore é finita, as finitas vidas que a compõem terminam em tempo finito quase certamente. Reciprocamente, se a população fica vazia em tempo finito, a não explosão garante que somente finitos indivíduos nasceram até esse instante; não haverá descendentes depois.
Pelo Teorema 4.11, \(q\) é o menor ponto fixo de \(f\) em \([0,1]\). A equação se fatora como
Se \(\lambda \leq \mu \), a outra raiz \(\mu /\lambda \) é pelo menos um, e a menor raiz no intervalo é um. Se \(\lambda \gt \mu \), essa raiz pertence a \((0,1)\) e é a menor. Finalmente, as \(k\) famílias precisam desaparecer para que o total desapareça; pela independência, a probabilidade é \(q^k\).
6.12.2 Quando chegam indivíduos de fora
Suponha agora que novos indivíduos cheguem por um processo de Poisson de taxa \(\nu \gt 0\), independente dos nascimentos e mortes da população. As taxas passam a ser
com \(d_0=0\). Usamos \(b_n,d_n\) nesta subseção para distinguir as taxas totais das taxas individuais \(\lambda ,\mu \). Em zero, o próximo evento é uma imigração; o estado deixou de ser absorvente.
Esse processo também não explode. Para ver isso, ignore as mortes e domine os nascimentos e imigrações por um processo cuja taxa, quando o total é \(n\), é \(c(n+1)\), com \(c=\lambda +\nu \). Se o total original é \(n\) e o total maior é \(m\), mantemos \(n\leq m\). Em uma tentativa do processo maior, aumentamos seu total em um e aceitamos também um nascimento ou imigração no processo original com probabilidade
Essa razão está entre zero e um, pois \(\lambda n+\nu \leq c(n+1)\leq c(m+1)\). As mortes só diminuem o total original, portanto a desigualdade entre os totais é preservada. Acrescentar um ao seu estado produz um processo de Yule de taxa \(c\), que não explode. Assim, em tempo limitado há apenas finitos nascimentos e imigrações no processo original. O número de mortes não pode exceder o total inicial mais esses nascimentos e imigrações. Portanto, o número de todos os eventos também é finito.
Todas as taxas de subida são positivas e as de descida são positivas fora de zero; logo, a cadeia é irredutível. Já verificamos a não explosão. Os pesos são exatamente os do Teorema 6.9. Falta justificar sua soma e, para calcular a média, a soma dos pesos multiplicados por \(n\).
O quociente entre pesos consecutivos satisfaz
Escolha um número \(r\) entre \(\rho \) e um. A partir de algum \(n_0\), temos \(w_{n+1}\leq r w_n\). Repetir a desigualdade dá \(w_{n_0+j}\leq w_{n_0}r^j\), e a cauda da série dos pesos é limitada por uma série geométrica convergente. Assim, \(C\lt \infty \) e o teorema citado fornece a estacionária.
A mesma comparação garante média finita. De fato,
Na última soma, usamos \(\sum r^j=1/(1-r)\) e \(\sum j r^j=r/(1-r)^2\). Essas identidades seguem da soma geométrica e de sua derivada para \(0\leq r\lt 1\).
Por construção dos pesos, o balanço detalhado em cada aresta é
Somamos em \(n\geq 0\). As duas somas são finitas pela integrabilidade que acabamos de provar; mudar o índice \(m=n+1\) no lado direito dá
Isolar a média fornece \(\nu /(\mu -\lambda )\).
Se \(\nu =\lambda \), cada fator do produto é \(\lambda (j+1)/[\mu (j+1)]=\rho \). Portanto \(w_n=\rho ^n\), \(C=1/(1-\rho )\) e \(\pi (n)=(1-\rho )\rho ^n\).
Considere taxas por dia \(\nu =1\), \(\mu =3\) e \(\lambda =1\). Os pesos são \((1/3)^n\), a estacionária é \(\pi (n)=(2/3)(1/3)^n\) e a média é \(1/2\) indivíduo. Se a reprodução individual aumenta para \(\lambda =2\), mantendo as outras taxas, os pesos passam a ser
cuja série continua convergente, mas a média sobe para \(1/(3-2)=1\). A entrada externa não mudou: a diferença vem dos descendentes produzidos depois da chegada.
O evento \(\{ X_t=0\} \) agora significa que a população está vazia naquele instante. Ele não significa extinção definitiva, porque uma chegada externa poderá repovoá-la. O modelo sem imigração e o modelo com imigração respondem, portanto, a perguntas diferentes sobre o desaparecimento.
6.12.3 Uma ponte para vidas que dependem da idade
As vidas exponenciais permitem descrever a população apenas pelo número de indivíduos: o tempo que cada um já viveu não altera sua espera residual. Com outras leis, essa redução pode deixar de funcionar. Por exemplo, se as vidas são uniformes entre um e dois anos, um indivíduo com poucos meses não morrerá nas próximas semanas, enquanto um que já viveu quase dois anos tem uma espera residual curta. Famílias nascidas em instantes diferentes podem ter o mesmo número de indivíduos e idades diferentes. A contagem sozinha deixa de distinguir essas situações e pode não conservar a informação necessária para prever o próximo intervalo.
Processos de Bellman–Harris permitem vidas com distribuição mais geral, seguidas de reprodução no fim da vida. Para acompanhar o mecanismo, precisamos guardar informações sobre as idades, ou usar ferramentas de renovação. Essa extensão mostra o papel da hipótese exponencial no modelo estudado aqui. A contagem e os relógios individuais voltam a ser uma escolha de estado que deve ser justificada.
6.13 Dormir, aguardar ou trabalhar*
Um equipamento pode consumir pouca energia enquanto dorme e mais energia quando está disponível para trabalhar. Acordá-lo frequentemente melhora sua disponibilidade, mas também altera o consumo. Vamos construir um modelo pequeno em que as duas quantidades podem ser calculadas.
O estado é \(D\) quando o equipamento dorme, \(P\) quando está pronto e \(T\) quando executa uma tarefa. As tentativas de chegada de tarefas formam um processo de Poisson de taxa \(\lambda \gt 0\). Uma tarefa é aceita somente em \(P\); nesse caso, começa imediatamente e o estado passa a \(T\). Tentativas em \(D\) ou em \(T\) são recusadas. Não há fila de espera.
Enquanto dorme, o equipamento acorda depois de um tempo exponencial de taxa \(\alpha \gt 0\) e passa a \(P\). Enquanto está pronto, um relógio independente de taxa \(\beta \gt 0\) pode mandá-lo dormir. Uma tarefa aceita exige serviço exponencial de taxa \(\mu \gt 0\); ao terminar, o equipamento volta a \(P\). Todos esses relógios, as chegadas e os novos sorteios após cada mudança são independentes. Os tempos exponenciais são hipóteses deste modelo simplificado; não descrevemos os temporizadores de um protocolo específico de comunicação.
Na ordem \(D,P,T\), o gerador é
Em \(D\), as tentativas recusadas não mudam o estado, e a única saída real é o despertar, de taxa \(\alpha \). Em \(P\), os relógios de dormir e de receber uma tarefa competem, dando saída total \(\beta +\lambda \). Em \(T\), a única mudança real é o fim do serviço, de taxa \(\mu \). Cada diagonal é o negativo da soma das outras entradas de sua linha.
O espaço é finito, todas as quatro taxas das setas são positivas e as setas ligam os três estados nos dois sentidos. Assim, a cadeia é irredutível e não explosiva. O balanço detalhado nas duas arestas exige
Logo \(\pi (D)=(\beta /\alpha )\pi (P)\) e \(\pi (T)=(\lambda /\mu )\pi (P)\). A normalização dá
fornecendo as três probabilidades. Como satisfazem o balanço detalhado, formam uma distribuição estacionária, pelo Teorema 6.8. Finalmente, em equilíbrio a potência é uma variável que assume os valores \(c_D,c_P,c_T\) com essas três probabilidades. Sua esperança é \(c_D\pi (D)+c_P\pi (P)+c_T\pi (T)\), que é a expressão anunciada.
A probabilidade de encontrar o equipamento pronto para aceitar uma tarefa, quando o estado observado tem lei estacionária, é \(\pi (P)\). O fluxo estacionário de tarefas aceitas é \(\lambda \pi (P)\): a taxa de transição \(P\to T\) é \(\lambda \). O mesmo balanço dá \(\lambda \pi (P)=\mu \pi (T)\), igualando os fluxos de início e de término de serviço. A potência calculada é uma esperança sob a lei estacionária.
Podemos tornar o compromisso do modelo explícito. Mantendo as outras taxas fixas, aumentar \(\alpha \) diminui \(\beta /\alpha \), portanto aumenta \(\pi (P)=1/L\) e o fluxo de tarefas aceitas. Se dormir consome menos que os outros dois estados, isto é, \(c_D\lt c_P\) e \(c_D\lt c_T\), escrevemos
O numerador da fração é positivo e permanece fixo; seu denominador diminui quando \(\alpha \) aumenta. Portanto, a potência esperada também aumenta. A melhoria no atendimento tem um custo de energia que o modelo permite quantificar.
Outra aplicação tecnológica é a redundância: um servidor reserva pode assumir o serviço quando o principal falha. A comutação automática pode falhar, pode haver intervenção manual e o servidor danificado pode ser reparado. O Exercício 6.22 propõe um modelo de quatro estados para construir o gerador e calcular previsões por uniformização. Ele separa três perguntas: se ocorreu perda definitiva, se o serviço está disponível no instante observado e se o serviço já sofreu alguma interrupção. Reparos tornam essas perguntas diferentes.
6.14 Exercícios complementares*
Os primeiros exercícios usam a Seção 6.9; os seguintes retomam as aplicações opcionais de ramificação, energia e redundância.
6.14.1 Ramificação, energia e redundância*
Determine a média da população no dia \(t\) e a probabilidade de extinção eventual.
Começando com um indivíduo, verifique pela equação da geradora que a probabilidade de extinção até \(t\) é
\[ q(t)=\frac{3(1-e^{-t})}{3-2e^{-t}}. \]Use-a para calcular a probabilidade de a população inicial de dois indivíduos ainda estar viva no dia \(t\).
Calcule o tamanho esperado no dia \(t\), condicionado a ainda haver indivíduos, e interprete o seu limite quando \(t\) cresce.
Determine as taxas totais a partir de \(n\), a distribuição estacionária, a probabilidade estacionária de população vazia e a média estacionária.
Se a taxa de imigração sobe para \(\nu =4\), mantendo as demais, escreva os pesos estacionários e calcule a nova média. Simplifique os pesos e sua soma para obter a probabilidade estacionária de vazio.
Explique por que, neste modelo com imigração, estar em zero em um instante não é o mesmo evento que a extinção definitiva do modelo sem imigração. Calcule a probabilidade de permanecer em zero durante mais de meio dia, partindo de zero, nos dois valores de \(\nu \).
Escreva \(Q\) e calcule a estacionária, a potência esperada em equilíbrio e o fluxo estacionário de tarefas aceitas.
Repita os cálculos quando \(\alpha \) é duplicada. Qual é o ganho no fluxo e qual é o aumento de potência esperada?
Suponha que o projetista substitua o despertar exponencial por um despertar que ocorre exatamente um minuto depois de entrar em \(D\). Explique por que os três estados já não conservam toda a informação necessária para prever o próximo intervalo.
Um servidor reserva: projeto computacional* Um serviço tem um servidor principal e um reserva. Use os estados: \(A\), principal funcionando e reserva pronto; \(B\), reserva funcionando enquanto o principal é reparado; \(M\), serviço interrompido enquanto se realiza comutação manual; \(F\), perda definitiva, um estado absorvente.
Em \(A\), o principal falha à taxa \(1/10\) por hora. Uma falha é seguida de comutação automática instantânea para \(B\) com probabilidade \(4/5\), ou exige comutação manual e leva a \(M\) com probabilidade \(1/5\). Em \(B\), o reparo termina à taxa \(1\) por hora e devolve o sistema a \(A\); o reserva falha à taxa \(1/5\) por hora e leva a \(F\). Em \(M\), a comutação manual termina à taxa \(2\) por hora e leva a \(B\); o reserva pode falhar antes dela, à taxa \(1/5\) por hora, levando a \(F\). Todos os tempos são exponenciais independentes e todos os novos sorteios também são independentes. Neste modelo, o reserva não falha enquanto aguarda em \(A\), e não há reparo nem recuperação a partir de \(F\). O serviço está disponível em \(A\) e \(B\). Comece em \(A\).
Construa \(Q\) na ordem \(A,B,M,F\), justificando inclusive as duas taxas que saem de \(A\).
Defina \(S(t)=\mathbb P_A(H_F\gt t)\), \(D(t)=\mathbb P_A(X_t\in \{ A,B\} )\) e \(I(t)=\mathbb P_A(H_{\{ M,F\} }\gt t)\). Explique as três medidas e prove \(I(t)\leq D(t)\leq S(t)\). Por que uma trajetória que entra em \(M\) e depois volta a \(B\) contribui diferentemente para elas?
Use uniformização com taxa \(\Lambda =3\) por hora para calcular as três medidas em \(t=1,5,10\) horas, com erro de truncamento inferior a \(10^{-6}\). Para \(S,D\), use a cadeia de quatro estados. Para \(I\), crie um estado absorvente de interrupção que reúna \(M\) e \(F\) assim que um deles é atingido. Justifique o controle do erro pela cauda de uma Poisson de média \(\Lambda t\).
Calcule \(E_AH_F\) e \(E_AH_{\{ M,F\} }\) por análise de primeiro passo. Explique por que mudar somente a taxa de comutação manual pode mudar \(S\) e \(D\), mas não muda \(I\).