Cadeias de Markov - Aula 2

e aí nós não passamos aprendemos o que é uma cadeia de markov então nos vemos que uma cadeia de markov produz representada por uma matriz essa matriz tem um conjunto de linhas e colunas essas linhas esses números 200 das minhas definem os estados da cadeia de markov então aqui nós temos todos os estados e as entradas referem a probabilidade de transição de um estado para o outro então por exemplo a probabilidade de sair do estado zero e do estado um então tô aqui no estado zero vou postar um essa chance e 0,3 duplo dois eu

tô aqui no estado ou o estado dois e 0,1 e assim sucessivamente então a gente pode representar a cadeia de markov por um grafo ou de azar essas definem as transições e esse e o peso das arestas definem a probabilidade de transição de um estado para o outro e nós vemos que essa cadeia o processo uma couve ano ele é totalmente caracterizado pela distribuição de um dos estados iniciais ou seja a probabilidade de começar em cada um desses estados e se eu conhecer conhecer essa probabilidade de começar em cada estado e conhecer a estrutura da

cadeia ou seja se conhecer essa matriz de probabilidade transição nós podemos caracterizar totalmente um processo marco viana bom então não tem o seguinte no fundo essa cadeia é usada para gerar um processo estocástico qual vai ser o processo estocástico o processo estocástico é uma sequência de estados resultantes dessa cadeia então qual seria uma sequência possível então por exemplo saiu do estado zero vou para o estado um do estado eu vou prestado dois do estado dois eu fico no estado dois fico no estado dois vou para o estado três do 3,0 fico do zero e vou

por um e assim sucessivamente então ó tem que isso aqui no fundo é uma série temporal então se eu colocar que os estados possíveis 0 1 2 e 3 o que que vai acontecer então por exemplo eu tô no estado zero do zero eu vou para um voo para o dois fico no dois fico no dois passa o estado 3 volto para o estado zero ficou no 0 vou para o estado um e assim acabei continua então não tem que no fundo essa cadeia ela gera uma série temporal e para que que serve isso uma

das possibilidades por exemplo é estudar como as pessoas geram as palavras e um texto então nós podemos pensar que cada um desses estados é uma palavra então quando nós temos uma frase nós temos uma uma transição de uma palavra para outra se nós pegarmos um livro e conseguimos estimar esses essas probabilidades essa é uma maneira muito fácil de tentar gerar uma sequência de estados ou seja gerar um texto é uma maneira muito fácil de tentar gerar um texto de forma artificial o mesmo pode ser feito com música nós podemos verificar as transições do dó e

ré oi e para o reparo se por exemplo e aí seguir nessa cadeia nós podemos tentar gerar uma sequência musical claro são maneiras muito simples que nem sempre condizem ao mundo real gente vai ver para certo aqui o texto não é tão trivial assim porque no fundo texto tem memória mas são maneiras muito simples da gente entender como que a gente pode aplicar essa cadeia no mundo real então na sala a gente vai aprender agora como calcular algumas propriedades mas antes disso lembre-se da propriedade fundamental qual que é a propriedade fundamental a probabilidade de eu

estar no estado ele mais um dado todo passado depende apenas do último estado ou seja a transição só depende do n por ele mais um tanta criado n-por-n mais um ela não depende do ele menos dois ele vem nos três até 10 então isso implica que o processo não tem memória ou seja o próximo passo só depende do passo atual antes de falarmos sobre as propriedades da cadeia pressão quem são os estados de uma cadeia de markov então nós olhamos nessa cadeia aqui que que vai acontecer se eu começar apresenta no a3 no estado três

eu posso ficar no estado 3 ou eu movo o estado ou é um outro estado 5 o seu como está no estado quatro ou eu fico nem citado várias vezes ou eu posso mover o estado cinco o estado dois então é o seguinte esses estados três e quatro eu posso ficar nesses estados mas se eu me mover por estado 13 estado 15 por dois outros cinco nós nunca mais voltamos a visitar esses estados então esses estados são chamados de transientes por quê porque eles são os estados que nós visitamos por um tempo e depois nunca

mais visitamos então os estados 3 e 4 são transientes e não tem que os estados 1 e 2 e 5 se eu entrar no nosso estado cinco eu nunca mais saio desse estado seu entrar no estado um ou dois eu também nunca mais saio porque eu fico transicionando aqui dentro bom então esses estados 12 e 5 são chamados de recorrentes então o estado um ou dois e os cinco são recorrentes e o estado cinco especialmente ele é um tipo de estado chamado absorvente porque absorvente porque a probabilidade de eu estar nesse estado é um ou

seja se eu chegar nesse estado eu nunca mais saio dele que seria um exemplo seria termos um computador que quando ele falha eles nunca mais voltam a funcionar entre o computador está funcionando transicionando de um estado para o outro se ele entra nesse estado aqui ele simplesmente para e nunca mais volta a funcionar então esse é um estado chamado absorvente nós vamos ver nas próximas aulas uma definição formal desses conceitos mas para essa aula nós precisamos apenas saber o que que é um estado absorvente porque esse é o estado que nós vamos tratar nessa aula

então lembre-se numa cadeia de markov nós podemos ter vários estados esses estados vão definir as classes depois nós vamos aprender a classificar esses estados mas por agora nós precisamos apenas saber que nós temos estados que são transientes e estados que são absorventes então nós estamos interessados nas seguintes nas seguintes perguntas então iniciando um vértice e então tem na cadeia eu tô num certo vértice e aí eu vou mudar eu vou transicionar para outros estados e uma pergunta é dado que eu comecei nesse estado e qual é a probabilidade de o visitar um estado j ou

seja qual é a chance de que ser constituiu ficar navegando por essa cadeia eu vou chegar em j parece que essa comunidade eu sempre bom quiser mas não ela pode ser essa qualidade pode ser nula porque vejam eu posso ter um caso e que aqui eu tenho estado cá e vejam que se eu escolhi e eu nunca vou estar o estado car por quê porque se eu chegar nesse sábado eu vou transformar para cá não tem como eu passar desse estado aqui para o estado do cartão seria zero outra propriedade importante é o tempo médio

para a absorção então gente viu que nós temos estados absorventes vamos supor que j é um estado absorvente ou seja bjj é igual a um nesse caso uma pergunta fundamental é quanto tempo eu demoro em média para chegar em j porque em média porque eu posso começar fica andando nessa cadeia vamos supor que tem outro caminho aqui eu fico andando e depois eu tive ó tá então em média quantos passos eu levo para chegar em j lembre-se o tempo aqui ele é discreto como a gente tá consertando o cadeias de markov de tempo discreto o

tempo ele é o tic do relógio ou seja eu começo um segundo dois segundos três segundos e assim vai a outra propriedade importante o número médio de visitas e tem imagina que nós temos aqui o estado e ele a pergunta básica é quantas vezes eu visito em média o estado l antes de ser absorvido por j então essa ideia então quantas vezes eu vou ficar andando aqui e aí eu visito esse estado tenho quantas vezes estado vai ser visitado em média antes de eu chegar no estado absorvente e nos veremos que basicamente o que nós

vamos usar é a lei da probabilidade total lembre-se a lei da probabilidade total relacionada com o teorema de mês é a parte que aparece nou denominador do teorema de vez e nós vamos usar por uma habilidade condicional então a partir de lei da probabilidade total probabilidade condicional nós vamos poder calcular todas essas propriedades de uma cadeia de markov estamos conservar o caso mais simples possível então nós temos aqui essa cadeia e aí vamos definir essa variável aleatória que ter que que ela é ele é um mínimo em n ou seja ele é um passo lembre-se

que hoje eu passo o old x = 0 ou x = 2 então ele é o tempo mínimo e que eu vou chegar no estado zero ou no estado dois ou seja que que eu tempo de absorção é o tempo que saindo do estado o que é o único estado que não é absorvente nota notem que essa probabilidade aqui é um porque ela é um porque a gente não tá vendo nenhuma seta saindo deles né se não tiver em uma certa saindo fica implícito que esse estado é absorvente e essa probabilidade é igual a um

então nós se eu começar no estado um eu vou terminar no estado zero ou eu vou terminar no estado dois então o que eu vou fazer eu vou usar o mínimo porque o mínimo é o número mínimo de passos que eu chego num dos dois então o que a gente vai fazer calcular a gente só quero poder calcular a probabilidade de absorção ou seja dado que eu comecei no estado um qual é a chance de eu terminar o estado zero e aí claro com a chance de terminar no estado 2 é a chance de determinado

estado zero porque só tenho dois estados possíveis aqui então a gente acha mais u d u e além disso a gente dá calcular o tempo médio até a absorção e o que que é isso é a esperança dessa variável aleatória que define o tempo até absorção dado que eu comecei no estado um ou seja é uma esperança condicional e ela chamasse esperança de ver vai calcular essa quantidade o que é a probabilidade de eu ser absorvido no estado zero dado comecei no estado um a gente vai vai usar uma técnica chamada análise do primeiro passo

essa análise do primeiro passo nada mais é do que a lei da probabilidade total a ideia seguinte eu vou simplesmente dar um passo e aí multiplicar o espaço que eu dei por essa probabilidade de esse passo então vamos escrever de novo aqui a nossa probabilidade então você ver como sendo a probabilidade de x t = 0 dado que fizer igual a 1 e agora vamos abrir isso aqui em termos da lei da probabilidade total então vai ser um somatório dica igual a zero e até dois porque eu tenho 012 estados da probabilidade de x =

0 dado que fizer igual a um porque eu sempre começo no estado um vírgula x1 = k vez a probabilidade de eu dar esse passo ou seja a chance de x1 = k dado que fizeram é igual a um então vamo abrir essa probabilidade aqui o primeiro treino vai ser fazer o que eu tô no estado um e ainda está num eu vou postar do zero então vamos lá que você a probabilidade de xp igual a zero ou seja a chance de eu terminar o estado zero dado que eu comecei no estado um me movi

para o estado zero às vezes a chance de eu sair do estado um e ir para o estado zero então contecc esse termo aqui vamos lá esse tempo aqui primeiro termo nossa em todo estado um vou por estar do zero e aí qual é a chance de eu terminar no estado zero essa chance aqui é um porque eu já estou está do zero e se eu entrar no estado zero não tem que eu nunca mais saio desse estado porque essa probabilidade aqui é um está do zero e o estado dois são absorventes então essa prioridade

é um ou seja olha a chance de eu terminar o estado 0 w que eu movi por estar do zero e aqui é a simplesmente a probabilidade de eu sair do estado um ir para o estado zero o próximo termo é a probabilidade de xtc igual a zero dado x0 = 1 x 1 em golão diz a probabilidade de x 1 é igual a um dado que fizeram é igual ao e quanto é que é essa probabilidade aqui para mudar bom se eu tô no estado um me movi para o estado um qual é a

chance de eu terminar em zero nota em seu no estado um de um passo e fiquei no estado um é a mesma coisa que eu começar o processo de novo porque vejam o processo não tem memória então na verdade ele não depende desse termo aqui porque por isso depende do último tempo lembre-se o processo markoviano o próximo passo só depende do passo atual então veja o passo atual é um x1 então para chegar no x no estado zero depende de mim depende da onde eu estou agora não dá onde eu estava anteriormente então no fundo

isso daqui é o próprio o é mesma coisa que eu começar de novo então lembre-se é esse que eu sincero mas eu dei um passo o xl esquece eu não tenho memória tá ok e aqui esse outro termo aqui é simplesmente o p1 que a chance de eu sair de uma transição do estado e ficar no estado um e o próximo termo quem que vai ser vai ser a probabilidade de x t = 0 dado x = 1 o x1 = 2 polegada de x 1 = 2 dado que fizeram é igual ao quanto que

é isso veja agora eu tô aqui no estado um eu vou me mover do estado dois qual é a chance de eu chegar no estado zero essa chance aqui vai ser zero porque vejo o estado dois ele absorvente se eu entrar nesse sábado eu não saio mais essa aqui é zero e esse tema que seria o p12 tava resolvendo nós temos que u&m é simplesmente tem 10 mas o xp um então a gente tem que o é simplesmente de 10 é dividido por 1 - p1 mas não tem o seguinte o que eu tenho p10

+ p1 + p2 essa soma desses termos tem que ser igual a um porque se eu somar essa probabilidade mas essa mais essa tem que ser um porque são os 3 links que estão saindo do estado um então eu tenho que 1 - p11 ele é simplesmente p10 + p2 ou seja posso escrever isso aqui como sendo p10 o / p10 + b12 então agora tirando o que 10 evidência simplificando a gente vai ter que isso aqui vai ser simplesmente um dividido por um mais o filme 2 / 10 totem e esse treino aqui se

o pneu zero for menor do que o tenho dois então escreveu que a maior do que 1 ou seja quanto menor p10 maior e esse termo então dividida por uma coisa maior menor é essa probabilidade que vai sentido ah e quanto maior for tem 10 menor é esse tempo de baixo maior na probabilidade então veja o quê é a chance de eu chegar no estado zero o estado 2 depende simplesmente dessas probabilidades não depende dessa probabilidade de ficar no estado um de acordo com essas prioridades nós chegamos mais facilmente nesse estado ou mais facilmente no

estado dois calculando agora a esperança do tempo médio têm absorção então a gente tem aqui uma esperança condicional e a ideia é exatamente fazer com a gente fez no caso da probabilidade só lembrando que nós podemos escrever a esperança de uma maratona x a gente pode usar a lei da esperança total e essa lei ela fala o seguinte esperança de tinta posso escrever como você não somatório y da esperança de x dado y vezes a probabilidade de y = y então a gente vai usar essa lei da esperança total então a gente pode escrever então

o que ver é simplesmente a além de ter entrado que fizeram = 12 novo vamos dar um passo e aí vamos usar essa regra aqui então vai dando um passo vai ser um somatório de k = 0 até 2 da esperança de ter dado que fizer igual a um vou dar um passo x1 = k e agora eu vou multiplicar pela probabilidade de dar esse passo ou seja a probabilidade de x 1 = k dado e fizeram igual e abrindo esses temos aqui então vamos lá então primeiro treino vai ser esperança de ter o dado

x = 1 o x1 = 0 x a probabilidade de x 1 x igual a zero dado que fizeram é igual a um então vamos lá já ver quem são esses temos aqui ó nossa e o seguinte qual é o tempo médio que eu demoro eu demoro para chegar no estado zero dado que eu me movi postar do zero tô dota eu tô aqui no estado um cheguei no estado zero quanto tempo em média eu levo para fazer isso eu levo simplesmente um passo então esse tema aqui é um tal vejo como o estado está

ligado diretamente com o estado zero então qual é o tempo médio para eu ir do estado um do estado zero é simplesmente um passo e aqui é simplesmente o p10 tô no caso do segundo termo então agora usando aqui cá igual seria a esperança de ter dado x 0 o irmão x1 = 1 vezes a probabilidade de x 1 x igual a um dado que fizeram igual tão não tem o seguinte agora que que vai acontecer se eu der um passo e ficar no mesmo lugar quantos passos em média eu preciso para ser absorvido em

0 ou se é absorvido em dois nós tem que trabalhar eu ter ele é o tempo de absorção ela não fala se você é absorvido em 0 ou em dois então nesse caso aqui que vai acontecer se eu der um passo e ficar no mesmo lugar então quanto tempo em média eu preciso até a absorção sem o de um passo e tem um mínimo vou precisar de um passo e aí quanto falta falta o tempo ver porque nós tem na hora que eu faço essa mudança então que acontece eu vou simplesmente remover esse e eu

dei um passo e aí quanto falta falta a mesma coisa que eu começar no mesmo lugar então falta o ver de novo então esse tema aqui o mais vezes a probabilidade de um mais e o último termo seria a esperança de ter dado que fizeram = 1 x 1 = 2 agora movimento o estado do ex vezes a probabilidade de x 1 c = 2 dado que fizeram é igual a quantos ser isso aqui bom você tem a mesma coisa que esse caso aqui do zero ou seja eu movi para o estado dois que absorvente

e tem quantos passos em média eu preciso para chegar no estado absorvente eu preciso só de um passo e esse aqui é o p12 então agora reescrevendo então a gente vai ter que ver é simplesmente ben 10 um mais um mais v o p1 mais 12 ou seja ver vai ser simplesmente tem 10 + 1 + 12 + vp1 então quanto que esse treino aqui sistema que vai dar um né porque eu tô somando essas três probabilidades então esse primeiro outro é um então eu vou ter que ver é simplesmente um mais vê um ou

seja ver é simplesmente um / 1 - p1 então o que que tá falando aqui tá falando o seguinte o tempo que eu vou demorar para ser absorvido em 0 ou em dois é inversamente proporcional a esse termo aqui se esse termo for igual a 1 que que vai acontecer eu nunca vou ser absorvida que é um tempo é bonito então veja um menos um vai dar 01 sobre 0 do infinito então eu nunca chego mas se esse tempo for zero quantos passos em média eu levo para ser absorvido apenas um passo então seria ver

igual a um por quê porque eu dou um passo ferro aqui então passa aqui ou seja se eu não te dei chance de ficar nesse estado' então esperado que o tempo seja realmente são passo então são alisando aqui gente viu tente calculou o tempo até a absorção começando no estado um e a gente calculou a probabilidade de ser absorvido no estado zero dado que comecei no estado um então agora como exercícios dia que vocês calculem a probabilidade de ser absorvido no estado dois dado que eu comecei no estado um e é esperado que esse valor

seja um menos essa probabilidade calculou então por que que é isso e seria o seguinte o gente absorvido em 0 ou absorvido em 2 ou seja a chance de ser servido em dois é um menos a chance de ser absorvida e zero e nós ver é bem que o tempo até a absorção tempo médio e inversamente proporcional a probabilidade de ficar na mesma estado então vamos lá então a gente tem essa cadeia aqui essa que esse que são os nossos estados eram 1 e 2 ea gente quer calcular de novo a chance de eu ser

absorvida em 10 dado que eu começo no estado um temos o estado um a chance de eu ficar neste estado e 0,6 a chance de eu ir para o estado zero é 0,1 o estado zero ele absorvente e a chance de eu ir para o estado 2 10 vírgula 3 e o estado dois também é absorvente então não tem para a gente fazer essa conta aqui a gente simplesmente usa o mesmo raciocínio e qual é o raciocínio é usar a lei da probabilidade total que a análise do primeiro passo de como é que eu faço

isso eu vou simplesmente começar no estado um e vou precisar do zero então simplesmente vou calcular a probabilidade dado que eu estou no estado um obsceno estado um dei um passo fui para o estado 10 vezes a chance de dar esse passo que é o p10 e mais a probabilidade deus é absorvido em zero dado que o comecei no estado um dei um passo e fiquei no estado um vezes a probabilidade p1 mais a probabilidade deus é absorvido 10 dado que o movido estado 2 e eu comecei no estado um vezes p12 mostramos que a

gente já sabe que é zero que a gente ter que em mim vai ser quanto e se fizer aqui a gente não precisa porque só depende do último o tempo está que acontece eu vou vir para o estado 10 qual a chance de eu terminar o estado zero essa chance é um p10 quanto que é o tem 10 tem 10 é 0,1 é mas esse aqui eu dei uma eu dei uma passo e fique no mesmo lugar ou seja o próprio o vez a chance de ficar no estado um que 0,6 então se a gente

resolver essa conta aqui vai ser simplesmente 0,1 / 1 - 0,6 que vai dar 0,4 então vai chegar aqui o é simplesmente um quarto que é de 25 porcento ou seja essa é a chance de que ter começado o estado um é a chance de ser absorvido estado zero então qual a chance de ser absorvido estado dois seria 75 por cento vamos então agora fazer o caso geral então vamos supor que nós temos estados 01 até ahi menos um são transientes e do erre até o n são absorventes ok então a gente vai ter um

conjunto de estados transientes e um conjunto de estados absorventes nota que eles são ordenados mas não necessariamente eles precisam estar ordenados vamos ordenar só para facilitar o nosso os nossos cálculos 101 até o estado é ruim menos um são estados transientes e do estado r&r mais um até o estado n são estados absorventes então até que a gente vai ter mesma coisa do erre até o menos um do erre até um ele esses aqui são usados sorvetes esse aqui são os estados transientes então o que a gente vai ter que a gente vai ter uma

matriz que é dividida em blocos e esses blocos vão definir as probabilidades entre esses estados então por exemplo nesse bloco que aqui ele representa as conexões ou seja as transições entre estados transientes para estados transientes nesse caso de transiente em para estado absorvente como se fosse por exemplo a transição do estado um pelo estado zero outro estado dois que a gente viu nos exemplos anteriores esse bloco aqui ó é a transição entre absorvente para transient então notem que o estado absorvente e aqueles estado que ele somente recebe conexões e a conexão que sai desse desse

estado fica no próprio estado ou seja a gente não tem conexões para qualquer outro estado então se eu tiver um link de um absorvente para transient esse absorvente não vai ser absorvente então no fundo as ligações entre absorvente para transient não existem então esse bloco aqui é uma matriz de zero só tem zero nesse bloco então não tem conexões de absorvente para transient desse caso aqui e a transição entre a absorvente e a absorvente mas nós temos seguinte a gente viu que o estado ele absorvente quando o p i é igual a 1 e qualquer

outro elemento é zero então no fundo os estados absorventes ele só tem conexões para ele mesmo então ele não tem conexões com absorventes que sejam diferente dele então no fundo essa matriz aqui ela é uma matriz diagonal onde a gente vai ter um na diagonal e zero fora dela então isso aqui é uma matriz identidade então com isso a gente vê que essa gente ordenada dessa forma os estados a gente vai ter uma matriz com uma forma bastante característica e agora então a gente pode calcular aquelas duas quantidades que é a probabilidade de sair do

estado ii esse absorvido no estado j ou o tempo que os que leva até ser absorvido dado que eu comecei num certo estado e vamos então resolver o caso geral então agora em vez de calcular por uma habilidade eo eu vou calcular a probabilidade eo com os índices e cá e o que quer dizer a probabilidade deus é absorvido no estado cardado que eu comecei no estado e tem o nosso em que cai o estado absorvente ter continua sendo a variável aleatória que representa o tempo até a absorção ea gente vai prender calcula também o

tempo médio até absorção dado que eu comecei no estado e então a gente representa por veículo então de novo vamos colocar aqui com os estados até o r menos um são estados transientes do r a t o n são estados absorventes e agora que tinha que fazer o que a gente tem que usar de novo análise do primeiro passo ou seja a lei da probabilidade total nota que importante aqui não é decorar as equações e sem aprender o raciocínio vocês como que eu resolvo por quê porque vejam o que a gente vai prender agora é

um caso que a gente tem ordenado mas a gente aprendeu o raciocínio a gente pode resolver qualquer caso isso é importante entender como calcular e não decorar os bom então vamos lá então vamos escrever aqui usando a lei da propriedade total ou análise o primeiro passo que wilka e nada mais receita o somatório o código a 0 e até ele e aí que que a gente vai fazer então a gente vai dar um passo então essa aqui vai ser um somatório da probabilidade de chester você colocar dado esse zero igual aí x1 = j vezes

a probabilidade de eu dar esse passo e quanto que é essa probabilidade ea probabilidade de x 1 x = j dado que fizeram é igual aí então agora vamos abrir somatório aqui e vamos considerar essa ordem da matriz então vai ser o quê que vai ser a prioridade de chester sei colocar dado que veja antes disso veja o seguinte esse termo que a gente não precisa por quê porque o processo markoviano ou seja ele depende apenas do último passo igual o último passo é o que eu passo o nosso aqui eu x1 então simplesmente x

t = k x 1 = 0 vezes a probabilidade de eu sair do noir e ir para o 10 e a probabilidade de xt se colocar x1 = 1 x a probabilidade de eu sair do noir e ir para o nome mais vários termos até o termo que considera r menos um porque o e menos um é o último estado transiente do vai ser probabilidade de xt segua cá dado que x1 é o estado r menos um vezes a probabilidade de sair do estado ii e ele para o estado r menos um aí o próximo

vai ser o que o próximo vai ser os estados absorventes ou seja transição do estado e para o outro estado j onde esse estado j agora é absorvente tá vai ser o que vai ser a probabilidade de um sair do estado e certo então vou chegar aqueles x t = k x1 = r a bença probabilidade de sair do estado um do sagui e ele está doer aí eu vou somar aí no meio que vai ter estado do cabo que eu cai absorvente então x t = k dado que x1 = k probabilidade de sair

de ir e dá um passo e chegar no estado do carro mas até o último estado que ela está doendo então x t = k um dado que fiz um igual a ele p&n então vamos lá então vamos ver o que que esses temos aqui represento então esse primeiro tempo aqui ele quer dizer o seguinte eu tô no estado zero no tempo um e eu quero chegar no estado cá então no fundo esse esse termo um aqui a gente viu que ele não importa por quê porque um processo na governo que não tem memória então

se tamo aqui na verdade ele é simplesmente ooo0 cá ou seja e a probabilidade de eu sair do estado zero esse absorvido no estado cá esse outro temos aqui a mesma coisa é u1k esse último tem uma mesma coisa então é u o que ri - 1k agora não até agora a gente entrou nos estados absorventes então quer dizer eu dou um passo para o estado absorvente qual é a chance de eu ser absorvido no estado cá dado que cai de frente dr percebendo que é sério e lembre-se eu chegar no estado por exemplo se

eu tenho aqui o estado ele é absorvente então tá todo mundo chegando dele então a chance dele não tem como eu ver se eu tiver um estado aqui e me aqui também é absorvente então notem que eu não tenho essa conexão entre lm então se eu chegar nesse estado e me não tem como chegar no estado l então aqui a mesma coisa ok então se eu chegar no estado do r e deu um passo para oeste aqueles absorvente não tem como chegar em casa e o caso de frente de ar mas aqui ó esse teu

irmão que quem queria dei um passo para o cá cheguei no estado do carro qual a chance de se absorver de cá é um e o último termo aqui é zero então notem que a gente pode escrever então todas essas esses temos aqui da seguinte forma que o nosso u a&k ele é simplesmente t i k o que é esse termo que queres um mais um somatório de quem dj igual a zero até r menos um da probabilidade de rj se você já eu vou mover de ir para j vezes u.j. cá eu vou ainda

a gente pode escrever isso aqui como sendo simplesmente wicca a de simplesmente p ficar mais um somatório em j e pertencente aos transientes a dp rj e o jk bom então essa aqui é a nossa probabilidade de sair do estado ii e chegar no estado cá então veja que agora a gente uma equação geral mas de novo não decore essa equação importante decorar o raciocínio ea gente pode usar essa equação agora pra gente calcular qualquer tipo de cadeia de markov que contenha um estado absorvente para calcular o tempo médio até absorção a gente usa a

mesma ideia ou seja essa que a nossa definição ou seja o tempo médio que eu levo para ser absorvido dado que eu comecei no estado ii então de novo se a gente escrever aqui vi a gente vai usar de novo análise do primeiro passo ou seja quiser j = 0 até n da esperança de ter dado que x 0 igual aí eu dou um passo para o estado j vezes a chance de dar esse passo ou seja a probabilidade de x 1 = j dado que fizer igual o que você gente abrir agora então vamos

lá de novo né 0 a t.r. menos um são os transientes a gr a t e n são os absorventes e aqui aqueles uma coisa tu vai trazer a gente aqui é absorvente então vamos lá então esse somatório vai ser contra vai ser esperança de ter dado de novo x 0 não lembro da gente não precisa usar por quê porque só depende do último passo que eu fiz um e tem um x 1 = 0 vezes a chance de eu sair do estado ii e ir pro estados j ou seja pe-01 mais a esperança de

ter dado x1 = 1 b e e postado um e assim vai até o último estado transiente que o estado r menos um então seria a esperança de ter dado que x1 é igual r menos 1 vez a probabilidade de eu ir no estado i para o estado r menos um mais e agora vem os absorventes a esperança de ter dado que x1 = r probabilidade de ir de ir para r e assim vai até o último estado que o estado n esperança de ter dado que x1 = ele p&l agora vamos notar o que

são esses valores aqui então nós temos seguinte ó nesse caso aqui eu saí do estado e fui para o estado zero e aí que acontece o estado zero é transient então eu ainda não cheguei no estado absorvente então quanto que falta para chegar no estado do estado absorvente então eu dei um passo e falta quem falta ov0 que a chance de eu sair do estado zero aqui é a mesma coisa e eu dei um passo para o estado transiente então eu tenho um passo e aí falta quanto falta o vê um ou seja é o

tempo médio para chegar no estado absorvente dado que comecei no estado um até esse último temos aqui que seria um mais vr menos um agora que a gente tem estados absorventes então quer dizer eu dei um passo e cheguei no estado absorvente tem quanto que é essa esperança é simplesmente um e o último também porque quer um porque eu vou direto para estado absorvente então eu passo aí cheguei no sabor de sorvete então agora a gente vê organizar aqui os nossos termos a gente vai chegar que ver aí ele vai ser simplesmente esses termos teus

aqui a gente pode escrever com você no somatório e tá vai ser um somatório de j = 0 e até r menos um de quem um mais pj p&j que eu simplesmente de ir para j mas e esses outros temos aqui que sobraram que que sobrou sobrou simplesmente a somatória das probabilidades que vai ser um somatório de j = r a t e n d p&j então bota assim como abrir primeiros o motor aqui se eu abrir que que vai acontecer mais um somatório de j = 0 até r menos um de pj mais um

somatório de j = 0 até r menos um dever j p j e mais o outro somatório de que já tava então somatório de j j = r até ele de p&j mas volta seguinte eu posso simplesmente agora juntar esses dois somatórios aqui ó esse somatório é a t.r. menos um esse aqui até menos um e esse aqui vai de rpm tem eu posso juntar esses dois somatórios aqui então se eu juntar esses dois somatórios eu posso escrever como sendo quem então vai ser simplesmente um somatório de j = 0 até ele de tj mais

um somatório de j = 0 a terra e menos um de pj pj e quanto que é seu somatório vejo eu tô somando disseram até ele ou seja tô somando todos os elementos da linha e trace temos aqui é um então a gente vai tirar então que eu ver aí e ele simplesmente um mais um somatório sobre os estados transientes ou seja j pertencente aos transientes de quem de pj pj ele tá agora a gente chegou a equação também para calcular o tempo médio até a absorção então vamos vamos brincar então a circulação negócio problema

que tinha resolveu então gente achou que a esperança de ter dado que fizer igual a um nesse caso aqui a simplesmente um / 1 - tem um e a gente calculou agora a equação para ver ir que era simplesmente um mais o somatório j pertencente aos transientes de pj um bj bom então vê se você coração funcione tão vejo o ver um ele vai ser quem ele vai ser simplesmente um mais quem que é transient nota 10 absorvente dois absorvente então só sobrou um então ele vai ser quem ele vai ser simplesmente p1 o j

= 1 x vi um então daqui eu tiro que daqui eu tiro que ver um é simplesmente um / 1 - p1 que é exatamente essa equação aqui então nota em que o nosso resultado pode ser usado para calcular qualquer caso ou seja dado qualquer cadeia desse tipo o quê que ela tenha pelo menos um estado absorvente não tem que ter pelo menos um nós podemos calcular o tempo para até absorção tempo médio até absorção dado que eu comecei no estado então responde agora aplicar a qualquer problema desse tipo e como costurar um exemplo onde

a gente aplicar esses conceitos que entraram nessa aula então a moeda lançada sucessivamente até que duas caras apareçam em sequência escreva a matriz de problemas transição determine o número médio de lançamentos necessários estão vejam que esse problema é o seguinte e tem imagine que eu tenho uma moeda e eu não sei essa moeda e saiu coroa por exemplo ou pode ter saído cara também mostrou seu coroa você saiu coroa no próximo lançamento pode sair cara ou pode sair coroa de novo no próximo lançamento pode sair cara pode sair coroa e aqui pode sair cara pode

sair coroa então não tem o seguinte que a gente vai fazer aqui então aqui seria por exemplo o lançamento n o ideal seria lançamento n e esse aqui seria o meu lançamento n + 1 e se ele pode ser qualquer valor tá desde zero até infinito então ele mais um e aí que que eu tenho aqui aqui eu tenho seguinte e nesse caso aqui que que aconteceu então saiu uma cara então você que seria um estado um o significado não tem uma carne seria o estado zero então do estado um eu posso ir para o

estado dois quando saiu duas caras ou eu posso retornar uma coroa eu vou buscar do zero de novo ou da coroa eu posso ir para cá eu vou para o estado um tão vejo o estado 0 estado um e aquecer o estado zero de novo então quê que seria o estado zero o estado zero seria por exemplo coroa coroa o estado um seria consequência seria coroa cara e o estado dois seria cara a cara então vejam então nós temos esses estados ou seja é quantas caras eu tenho até o lançamento atual então nós temos momento

atual por exemplo eu tenho uma cara ou nenhuma cara e aí para o próximo lançamento ou seja o próximo resultado eu posso ter duas caras quando tem essa sequência aqui ou eu posso retirar a primeira cara não posso simplesmente continuar com coroa então como é que vai ser essa momento essa minha matriz você nem matriz ela vai ter simplesmente três estados ou seja os estados 0 1 e 2 e o que que esses estados representam os representam o número de cargas em sequência até o lançamento n então a gente pode escrever nossa matriz p também

vai seus estados 0 1 e 2 então 0 1 e 2 nossa então isso é esses essas linhas representam o número de caras até o lançamento n então até o lançamento hélio vocês vão colocar em questão representa por lançamento n e esses valores aqui são pro vazamento em animais um então beijo se eu tô no estado do zero ou seja no estado zero que que eu posso fazer no próximo lançamento eu posso ter uma cara eu posso continuar sem nenhuma cara na sequência o tempo solicitado um ou eu posso continuar no estado zero então que

se sai coroa é meio não ter e aí eu posso emprestado um com chance meio quando saiu uma cara e não posso estar dois se eu tiver no estado o que pode acontecer eu posso do estado dois quando sair outra cara então eu tenho o caso cara cara que eu quero encontrar ou eu posso sair coroa e voltar para o estado zero então do estado eu posso voltar para o estado do zero ou eu posso do estado dois não tem chance de ficar no estado um e o estado dois ao estado absorvente porque simplesmente termina

o jogo bom então agora calculado tem que ficar com talvez zero porque eu começo sem nenhuma cara ele é simplesmente a esperança de ter dado que fizeram é igual a zero então usando aqui haddad o primeiro passo entender quem e simplesmente o somatório de k = 0 até 2 de quem da esperança de ter o dado x = 0 x1 = k vezes a probabilidade de sair do estado zero ir para o estado cá ou seja esse tema que já sabe que a gente não usa porque só depende do último passo e traça esperança essa

esperança de ter dado x 1 = 0 xp 00 mais a esperança de o resultado que x1 = 1 pe-01 mais a esperança de ter dado que x1 = 2 vezes p02 então quanto é que vai dar os exércitos tem que ver zero vai ser simplesmente quanto bom se eu der um passo ir para o estado do zero que aconteceu eu simplesmente todo estado zero então passe continua no estado zero então nós tem que aqui vai ter que continuar saindo cara ou coroa e vejam que só que pode ser continuar indefinidamente ok então o que

que aconteceu então eu tenho passo e quanto falta eu voltei para estar do zero então simplesmente um mais de 0 e vezes essa probabilidade que é meio porque a moeda é justa mais nesse caso aqui que que aconteceu eu tenho passo e pus fui para o estado um ou seja eu tô no estado eu vou precisar de um só condensado o que acontece pode sair cara eu emprestado dois ou posso continuar no estado zero então é simplesmente um mais ver um vezes meio e esse último treino aqui é zero porque porque essa probabilidade aqui é

sério ok então na verdade essa probabilidade aqui é zero então daqui eu tiro que o v0 ele simplesmente enquanto bom que vai ser meio aqui eu tenho outro meio meio mais meio vai dar um mais v 0 sobre 2 mais vinham sobre 2 a dizer sobre 2 mais vi um sobre dois e talvez eu tenho calcular agora o meu tá me coloquem que vão ver um a esperança de ter dado que fizeram é igual a um agora usando de novo análise primeiro passo o que é a lei da probabilidade total cai com a 0 até

2 da esperança de ter dado e fizeram = 1 x 1 = k propriedade deus do estado um postado cá então vamo abrir isso aqui então vai ser quanto vai ser simplesmente esperança de ter dado x 1 = 0 p zero mais a esperança de ter o dado x1 é bom p hummm hummm hummm mais a esperança de ter dado x1 = 2 b12 e daqui eu tiro que ver um vai ser quatro vejam se eu mover para o estado zero então eu tô aqui no estado um eu posso estar do zero quando sai outra

coroa posso e aí eu volto busca do zero ou seja qual é o tempo que eu preciso quanto tempo falta para chegar às absorvente o passo que eu dei mais v0 vezes meio esse termo aqui o p1 ele é zero porque não tem chance de eu continuar no estado um então não tem que ser termo que zero e esse termo que que acontece aqui eu tô no estado um e aí eu saio uma coisa cara então vou postar dois e termina ou seja felizmente um passo de uma vezes é uma vezes meio então daqui eu

tiro que ver um é simplesmente o meio então ser meio mais meio então simplesmente um mas a 0 sobre dois então agora substituindo então eu vou ter que ir ver zero então portanto ov0 ele é simplesmente um mais de 0 sobre 2 mais o meio vezes um mais a 0 sobre dois ou seja de 0 é simplesmente um mais v052 mais meio mais 10 sobre quatro vamos tirar quem a 0 em evidência então vai ser de 0 x1 - 6 - 4 = quanto é igual o mais meio três meses bom então aqui eu tiro

que ver zero vezes o mc que vai dar quatro então o primeiro tempo por ser 4 - 2 - 1 isso aqui é igual a três meses dizendo que eu tiro que fizeram vai ser quanto bom que vai ser 4 - 3 vai dar um eu passo quatro multiplicando e vai ser três vezes quatro subir dois então aqui eu tiro que v0 eu simplesmente eu tiver 26 lançamentos e o que que você valor seis quer dizer imagine o seguinte imagina que nós temos uma moeda então a gente vai lançar essa moeda várias vezes então vai

ter uma sequência de casas e coroas e a gente vai lançar até que saia sequência cara a cara aí eu vou contar quantos lançamentos eu precisei ou seja se vai ser o meu de ir para o experimento ii e o valor v0 estimado eu repito esse experimento ele vezes e dele vai ser um somatório de igual a 1 até n de t.i. / ele então agora a gente pode fazer isso em paz então como é que eu vou fazer em paz eu vou simplesmente falar aqui um é cara zera coroa vou sortear números 01 até

que a sequência um apareça ou seja duas caras faço isso por exemplo seis vezes vou contar quantos lançamentos eu precisei em cada experimento soma-se número de lançamentos e / sem então você sabe fazer é isso e aí por uma moeda justa eu espero que esse valor seja próximo de 6 então se moeda for justa eu espero precisar em média seis lançamentos para que sequência cara a cara ocorra sumarizando então o que a gente vê nessa aula então gente aprendeu nessa aula sobre análise do primeiro passo e do a gente aprendeu a calcular o nosso ficar

que querer esse oi cara é a probabilidade deus é absorvido no estado cá dado que eu comecei e no estado ii e a gente aprendeu calcular o vi quem que eu vi o número médio de passos que eu preciso até a absorção dado que eu comecei no estado e então gente aprender a calcular essas duas propriedades a gente viu que a gente pode calcular para qualquer tipo de cadeia de markov na verdade para qualquer cadeia de markov que contenha pelo menos um estado absorvente e com isso a gente pode agora aplicar em vários tipos de

problemas então como leitura adicional e surgiram capítulo 3 desse livro aqui que é o livro do outeiro e karen dei uma olhada nesse livro e aí vai ter vários exemplos é importante olhar sempre os exemplos porque a gente se consegue sempre aprender com os exemplos mas sempre tenho em mente que não adianta decorar as equações é preciso aprender o raciocínio ea preciso sempre interpretar os resultados para verificar se os resultados fazem sentido e [Música]