Análise de Cadeias de Markov: Modelos de Transição e Distribuições Invariantes

Questão 1 Os motores de busca O internauta escolhe a próxima página para ver selecionando com igual probabilidade a partir das páginas apontadas pela página atual Se uma página não tem qualquer ligação de saída por exemplo página 2 em seguida o interessado seleciona qualquer uma das páginas do universo com igual probabilidade Poderíamos estar interessados em encontrar a probabilidade de que o internauta veja a iésima página Se a página atual aponta para k páginas então a próxima página é selecionada a partir desse grupo com probabilidade 1k Se a página atual não aponta para nenhuma página então a próxima página pode ser qualquer uma das cinco páginas com probabilidade de transição 15 a Construa uma cadeia da Markov para esse problema E 12345 Xn é a nésima página visualizada 0 12 12 0 0 15 15 15 15 15 13 13 0 13 0 0 0 0 0 1 0 0 12 12 0 b Construa o grafo de transição e verifique se a cadeia é irredutível e aperiódica Temos C1 12345 pois P1212 e P2115 12 P2315 e P3213 23 P3413 e P432 P41 P5312 34 e P451 e P5412 45 Logo a cadeia é irredutível Como P2215 looping d2 mdc 1231Sendo uma única classe segue que d1d2d3d4d51 logo a cadeia é aperiódica c Obtenha a distribuição invariante e interprete no contexto do problema ΠP Π Π1 Π2 Π3 Π4 Π5 0 12 12 0 0 15 15 15 15 15 13 13 0 13 0 0 0 0 0 1 0 0 12 12 0 Π1 Π2 Π3 Π4 Π5 Π25Π33 Π1 12 Π115Π213Π3 Π2 12 Π115Π212Π5 Π3 15 Π213Π312Π5 Π4 15 Π21Π4 Π5 Π1Π2Π3Π4Π51 Usando Wolfram Π232 Π1 Π32110 Π1 Π42310 Π1 Π4135 Π1 Substituindo em 6 Π1 32 Π12110 Π12310 Π1135 Π1 1 13221102310135 Π11 101521232610 Π11 Π11095 Π23210951595 Π3211010952195 Π4231010952395 Π513510952695 Π10951595 2195 2395 2695 Usamos o teorema ergódico as proporções de visitas a longo prazo as páginas 12345 são respectivamente 1053 1579 2111 2421 e 2737 Questão 2 Um jogador tem um R 100 e a cada vez rodada que joga ganha R100 com probabilidade 04 ou perde R100 com probabilidade 06 O jogo termina quando o jogador acumula R 300 ou R 000 Este jogo é uma Cadeia de Markov cujos estados representam a quantia que o jogador possui a cada vez que joga após cada rodada a Matriz e grafo de transição E 0123 1 0 0 0 06 0 04 0 0 06 0 04 0 0 0 1 b Sim é possível Uma situação periódica Ou o jogo acaba ou se renova c P105 P12 P21P12P21P1004x06x04x06x06003456 d Note que no item b o jogador termina sem dinheiro quando o jogo acaba em uma rodada ímpar Seja A o evento em questão PAE PA2K1 onde A2K1 é o evento onde o jogo termina na rodada 2k1 PA1P1006 PA3P12XP21XP1004x06x0604x062 PA5P12XP21XP12XP21XP1004x06x04x06x06042x062 Questão 1 extra 316 116 12 38 12 18 38 38 14 P2PxP 716 116 12 38 12 18 38 38 14 x 716 116 12 38 12 18 38 38 14 103256 63256 45128 51128 41128 932 51128 39128 1964 P3P2xP 103256 63256 45128 51128 41128 932 51128 39128 1964 x 716 116 12 38 12 18 38 38 14 16394096 11474096 6552048 8192048 5952048 3171024 8192048 5912048 3191024 PX31X02 P213 81920480399 Questão Uma partícula deslocase sobre uma circunferência parando em três pontos previamente marcados no sentido dos ponteiros do relógio 12 e 3 Em cada passo a partícula deslocase nos sentidos nos ponteiros com probabilidade 08 e no sentido contrário com probabilidade 02 Seja para n E N Xn a posição da partícula no instante n a Obtenha a matriz e grafo de transição P 0 08 02 02 0 08 08 02 0 b Obtenha e interprete caso exista a distribuição invariante ΠP Π Π1 Π2 Π3 0 08 02 02 0 08 08 02 0 Π1 Π2 Π3 02 Π208 Π3 Π1 08 Π102 Π3 Π2 02 Π108 Π2 Π3 Π1Π2Π31 Substituindo 1 em 2 08 02 Π208 Π302 Π3 Π2 016 Π2064 Π302 Π3 Π2 084 Π3 Π2016 Π2 084 Π3 084 Π2 Π2 Π3 Voltando em 1 02 Π208 Π3 Π1 02 Π208 Π2 Π1 Π2 Π1 Logo Π1Π2Π31 Π1 Π1 Π11 Π113 Π213 Π313 A distribuição invariante é Π 13 13 13 Se escolhermos o estado inicial de acordo com a distribuição invariante está será a distribuição do processo em todo instante Isto é se Π0 Π 13 13 13 então Pn Π para todo n Questão X Um estudo de resposta imunológica em coelhos classificou os coelhos em quatro grupos 123 ou 4 de acordo com a intensidade da resposta imune De uma semana para a seguinte os coelhos alteram a classificação de um grupo para o outro de acordo com a seguinte matriz de transição 57 27 0 0 0 12 13 16 0 0 12 12 0 0 14 34 a Suponha que um coelho inicie no grupo 1 Qual a probabilidade de quatro semanas depois ele estar no grupo 2 P124 P11 P11 P11 P12 P11 P11 P12 P22 P11 P12 P22 P22 P12 P22 P22 P22P113 P12P122 P12 P22 P11 P12P222 P12P223573275732712 57127122271232502401506861019625625339604026 b Suponha que um coelho inicie no grupo 1 Em média quantas semanas ele permanecerá nos grupos 1 ou 2 Note que C11 C22 C334 Seja N o número de semanas que o processo permanece nos grupos 1 e 2 NT1T2 onde T1 é o tempo de permanência no estado 1 e T2 é o tempo de permanência no estado 2 Note que T1 e T2 são independentes Para K112 K212 PT1K1 P11 P11 K11 vezes P12 57K11 27 K112 PT2K2 P22 P22 K21 vezes P23 P24 12K21 1316 12 K21 12 K212 Tome K2 PNKPT1 T2K 𝑘1 𝑃 𝑇1 𝑗 𝑇2 𝑘 𝑗 𝑗1 𝑖𝑛𝑑 𝑃 𝑇1 𝑘1 𝑗1 𝑗 𝑇2 𝑘 𝑗 57𝒋 𝟏 2712𝒌 𝒋 𝟏 12 𝑘1 𝑗1 5 𝑘1 𝑗1 7𝒋57 17 12𝒌 𝟏12𝒋 5 7 1 2𝒋 17 75 1 2 𝒌 𝟏 𝑘1 𝑗1 1512k1 10 7 𝒋 1 5 2 1 2 𝒌 𝑘1 𝑗1 10 7 𝒋 mas S1071072107k1 107S10721073107k 1071S107K10 7 37S107k107 S73 107k107 PNK 25 12k 73107k107 141512k107k107 141510712k107k114312k107k11 logo PNK 4312k 107k11 k23 EN 𝑘𝑃 𝑘 𝑘 4 3 1 2 𝒌 10 7 𝒌 𝟏 1 112 𝐼𝑁𝐹𝐼 𝑘2 Questão 6 Em um domingo ensolarado de primavera uma empresa de minigolfe pode obter R 2000 de receita bruta Se o dia estiver nublado a receita cai 20 Um dia chuvoso reduz a receita em 80 Se o dia de hoje estiver ensolarado há 80 de chance que amanhã também o tempo estará ensolarado sem nenhuma chance de chuva Se o dia estiver nublado há 20 de chance de chover amanhã e 30 de chance de fazer sol A chuva continuará no dia seguinte com uma probabilidade de 08 mas há 10 de chance de fazer sol Determine a receita esperada por esta empresa Ensolarado1 nublado2 e chuvoso3 Matriz P 08 02 0 03 05 02 01 01 08 ΠP Π Π1 Π2 Π3 08 02 0 03 05 02 01 01 08 Π1 Π2 Π3 810 Π1310 Π2110 Π3 Π1 210 Π1310 Π2110 Π3 Π2 210 Π2810 Π3 Π3 Π1Π2Π31 210 Π2810 Π3 Π3 210 Π2Π3 810Π3 210 Π2210Π3 Π2Π3 Em 1 810 Π1310 Π2110 Π2 Π1 810 Π1410 Π2 Π1 04 Π2 Π108 Π1 04 Π2 02 Π1 Π12 Π1 Em 4 Π1Π2Π31 2Π2Π2Π21 Π2025 Π3025 Π12 Π12x025050 Π 12 14 ¼ ET1X011122 ET2X021144 ET3X031144 RS200000 RN 1600 RC 400 ER2x20004x16004x40012000 Questão Sete meninos estão brincando com uma bola O primeiro menino sempre a lança para o segundo menino O segundo menino tem a mesma probabilidade de jogá la para o terceiro ou o sétimo O terceiro rapaz mantém a bola se ele a receber O quarto menino sempre a joga para o sexto O quinto menino tem a mesma probabilidade de jogála para o quarto sexto ou sétimo menino O sexto menino sempre lançala para o quarto O sétimo menino tem a mesma probabilidade de jogála para o primeiro ou quarto menino a Modele este problema como uma Cadeia de Markov Escreva o espaço de estados matriz de transição e faça um grafo de transição b Classifique cada estado em recorrente ou transiente c Faça a construção de classes para os estados dessa cadeia Verifique se a cadeia é irredutível Questão O mundo de Oz é abençoado com muitas coisas dentre as quais não se encontra o tempo Seus habitantes nunca têm dois dias de sol consecutivos Depois de um dia bom eles são igualmente propensos a ter um dia de chuva ou um dia de neve Se eles têm chuva ou neve num dia há uma chance de 50 de terem o mesmo no dia seguinte Se há mudança do tempo após um dia chuvoso ou com neve esta mudança é para um dia bom em apenas 50 das vezes A Determine a matriz de transição Estados 0 dia de sol 1 dia de chuva 2 dia de neve Matriz P 0 12 12 14 12 14 14 14 12 b A longo prazo qual a porcentagem de dias ensolarados chuvosos e com neve Questão Suponha que temos duas caixas rotuladas 1 e 2 e também 3 bolas rotuladas por 1 2 3 Inicialmente algumas das bolas estão na caixa 1 e as restantes estão na caixa 2 Um número inteiro é escolhido aleatoriamente de 1 2 3 e a bola marcada por esse inteiro e removida de sua caixa Vamos agora selecionar aleatoriamente uma das duas caixas e colocar a bola removida nessa caixa O procedimento é repetido indefinidamente e as seleções são realizadas de forma independente Denamos Xn como o numero de bolas na caixa 1 apos o nesimo experimento a Descreva uma Cadeia de Markov para este processo b Verique se a cadeia e irredutvel e aperiodica E necessario justicar c Encontre a distribuicao invariante para este processo De tres interpretacoes Considere uma Cadeia de Markov Xn com espaço de estados E 1234 e matriz de transição P 0 13 0 12 13 0 12 0 0 12 0 13 13 0 12 0 a Obtenha πj para todo i j E b Verifique se esta matriz é irreducível e aperiódica Justifique c Seja T2 minn 0 Xn 2 Obtenha PT2 k X0 1 e ET2 X0 1 Um ratinho ocupa inicialmente a gaiola 1 e é treinado para mudar de gaiola atravessando uma porta sempre que soa um alarme Cada vez que soa o alarme o ratinho escolhe qualquer uma das portas incidentes a sua gaiola com igual probabilidade e sem ser afetado por escolhas anteriores Considere que o alarme ficou programado para tocar a cada minuto a Determine a probabilidade de o ratinho estar na gaiola 3 após ter soado o alarme 3 vezes b Qual a distribuição da proporção de vezes que esse ratinho passou pelas gaiolas considerando um longo lapso temporal Considere uma Cadeia de Markov Xn com espaço de estados E 1234 e probabilidades de transição Pij 13 1 i 3 Pii 16 e Pij 12 se i j a Obtenha a e o de duas interpretações para a distribuição invariante b Obtenha e interprete ET1 X0 1 para i E c o que se pode concluir sobre limn Vn Interprete o resultado b πP π π1 π2 π3 π1 π2 π3 04 π2 06 π3 π1 06 π2 04 π3 π2 04 π1 06 π2 π3 5 5 6 1 1 Questão 4 Considere uma Cadeia de Markov com espaço de estados E 1 2 3 e matriz de transição P 0 1 0 0 0 2 0 0 0 0 0 0 0 0 1 0 a Obtenha pi para todo i E b Obtenha a distribuição de Xn sabendo que estado inicial é escolhido de acordo com a distribuição Π0 π01 π02 π03 PX0 1 PX0 2 PX0 3 c PX0 3 1 7 1 2 3 c Obtenha e interprete a distribuição invariantes Π Questão 4 Considere uma Cadeia de Markov Xnn0 com espaço de estados E 1 2 3 4 e probabilidades de transição Pi i1 1 i 1 3 Pi i1 1 i 2 4 P1 1 23 2 i 4 P1 4 13 a Construa a matriz de transição e gráfico da trajetória para esse modelo b Calcule PX3 2X0 1 c Obtenha e interprete a distribuição invariantes Um ratinho ocupa inicialmente a gaiola 1 e é treinado para mudar de gaiola demonstrando uma pata sempre que saca um alarme Cada vez que saca o alarme o ratinho escolhe qual de uma das patas incidentes a sua gaiola com igual probabilidade e sem se fixar por estados anteriores Considerando que ao pegar o cada minuto a Bajo vm o mínimo de viri tas os estados i e j o alarme sean o vago O que se pode concluir sobre vm Interprete b defino Txminnso xni Obtendo ETnXo1 Salvações p 0 12 12 13 0 23 0 13 13 0 T π1 π2 π3 π π1 π2 π3 T1 π2 π3 π1 π2 π3 13 π2 13 π3 π1 1 12 π1 23 π3 π2 2 π1 π2 π3 1 3 π2 π3 3π1 3π1 π2 π3 0 5 3π1 4π3 π2 3π1 6π2 4π3 0 6 5 6 1 5π2 π3 0 5π2 5π3 π2 π3 Assim π1 π2 π3 1 2π2 3π2 3π2 8 8π2 3 π2 38 π3 38 a Vdm cm π1 2 8 14 y1m 1 14 14 c 1 y Vdm I ε I ε ε Grafo de transição p 0 2 3 4 5 0 0 4 0 1 0 0 0 0 5 4 1 0 0 4 5 0 0 0 4 5 b ϕX3 2X0 1 p12 p13 p22 p12 p23 45 15 15 15 5 1 4 4 4 5 1 15 15 1125 0152 π π1 π2 π3 π4 π ct T1 T2 T3 T4 15 π1 T1 15 π2π3 4π3 4π2 5π3 T1 T2 T3 1 T3 T4 T4 a Representar o estado discreto que resulta de uma cadeia de Markov deixando claro as suas hipóteses E 0 1 2 3