fundo
Estou estudando coincidências comuns e coincidências "próximas" que, no entanto (indevidamente) impressionam a pessoa comum. A pergunta abaixo é uma extensão do famoso problema do aniversário , que pergunta "Quantas pessoas, escolhidas aleatoriamente, são necessárias para que haja 50% de chance de duas delas compartilharem o mesmo aniversário?" A resposta é . (Na verdade, é um pouco mais baixo se alguém incorpora o fato de que os aniversários não são distribuídos uniformemente ao longo do ano, mas sim "se acumula" em alguns meses, aumentando assim a probabilidade de duas pessoas compartilharem o mesmo aniversário.) Se alguém relaxa a condição e permite a coincidência "quase" de ter o mesmo aniversário ou diferir por um dia , a resposta cai para apenas ,
O abaixo é uma extensão do problema de aniversário, mas mais interessante e complicado.
Quantos americanos, escolhidos aleatoriamente, são necessários para ter uma chance de 50% de que dois deles vivam em a) no mesmo estado ou b) no mesmo estado ou em um estado adjacente?
Suponha que recebamos uma lista dos 50 estados com suas populações:
bem como uma matriz de adjacência (ou gráfico não direcionado ) contendo as informações de adjacência de estado (incluindo auto-adjacências), ou seja, compartilhe uma borda:
.
Observe que queremos resolver esse problema computando com probabilidades condicionais e sem recorrer a simulações estocásticas. Uma abordagem tão rigorosa é baseada em princípios e generaliza mais naturalmente a problemas muito grandes.
A abordagem para a) será uma generalização do problema do aniversário, mas a resposta para b) parece um pouco mais complicada.
Estou procurando apenas as equações (e explicações). Posso então calcular os valores numéricos usando dados censitários e geográficos.
Observarei aqui que, através da pesquisa estocástica, a resposta para b) é a (talvez surpreendente) apenas 3,5 pessoas. Com 4 pessoas, as chances são de quase 60%, pelo menos duas são do mesmo estado ou de estados vizinhos.
fonte
Respostas:
Responderei à pergunta b) porque é mais geral, e a questão a) pode ser pensada como um caso especial de b) onde a matriz de adjacência é simplesmente a matriz de identidade. Vou dar o método exato, embora métodos aproximados possam ser necessários, porque o cálculo da solução exata é escalado rapidamente com o número de pessoas. Não acho que exista uma solução que dimensione melhor, mas talvez alguém possa me corrigir.
Ajuda a analisar o caso explícito de um pequeno número de pessoas, adicionando mais e procurando o padrão.
Vamos começar com a probabilidade de estados adjacentes para duas pessoas. A probabilidade de a primeira pessoa estar no estado e a segunda pessoa no estado é que que é o número de pessoas no estado eEles são adjacentes se onde é o ésimo elemento da matriz de adjacência. Portanto, a probabilidade de que eles sejam adjacentes é:i j
Vamos olhar para pessoas. É fácil ver que, No entanto, agora também é fácil ver por que esse cálculo pode se tornar intratável para um grande número de pessoas. O exposto acima não pode ser fatorado em termos de porque e devem aparecer nas somas , portanto, um processo indutivo com o qual determinamos em termos de parece estar fora da pergunta. Ele deve ser resolvido explicitamente para qualquer valor. No entanto, como eu fiz no caso de pessoas, geralmente você pode pegar o "triângulo retângulo" superior da3
Para pessoas, A segunda linha reduz de uma soma em termos de para uma soma em termos, que ainda é muito ruim. Além disso, cada termo envolve um produto acima de fatores. Portanto, no geral, esta é uma computação . Se ignorarmos a adjacência e respondermos à pergunta (a), ela se tornarám
fonte
É possível resolver isso usando Matrizes de Markov para modelar o processo aleatório de seleção de pessoas. Essa abordagem exige bastante esforço de configuração, mas possui uma maneira estruturada de obter sua resposta.
As matrizes de Markov são usadas para modelar um processo aleatório que pode se mover entre "estados" discretos (para evitar confusão entre os estados dos EUA e os estados de markov, irei me referir aos estados de markov como "Fases").
Nesse contexto, a fase markov é a lista de todos os estados dos quais você escolheu os americanos. Por exemplo, se o primeiro americano for de Washington, a fase será {WA}, e se o próximo americano for do Texas, a fase será {TX, WA}. O pedido em que você escolheu as pessoas é irrelevante, portanto {TX, WA} é a mesma fase que {WA, TX}.
Antes do início da amostragem, começamos na fase {0} em que nenhum americano foi escolhido. Definimos uma única fase {E} (que significa "final") em que você escolheu dois americanos de estados adjacentes, o processo aleatório de escolher americanos continua até que {E} seja alcançado. Continuando da fase {TX, WA}, se o próximo americano for do Oregon, a fase passará para {E}, já que o Oregon fica ao lado de Washington.
{E} é conhecido como "estado absorvente" porque, uma vez que o processo aleatório atinge {E}, ele não pode mudar para uma fase diferente.
Você deve criar uma lista de todas as fases possíveis que podem ocorrer antes de atingir {E}.
Agora você precisa calcular a matriz de Markov para a probabilidade de transição entre estados. Antes de tudo, seja o vetor de probabilidades de amostrar um americano de um estado. Então é a chance de escolher alguém da Flórida.M P Pflorida
As entradas na matriz de Markov são a probabilidade de transição da fase para a fase . Por exemplo, fazer a transição de {WA} para {TX, WA} é . A probabilidade de transição de {WA} para {E} é . E a probabilidade de fazer a transição de {E} para {E} é 1.Mij i j PTexas PWashington+PIdaho+POregon
Você sempre inicia a amostragem a partir de {0}. Após a amostragem de 1 americano, a probabilidade de estar em {E} é . Após a amostragem de 2 americanos, a probabilidade de estar em {E} é (A matriz M é multiplicada por si mesma e, em seguida, você obtém a probabilidade na linha {0 } e coluna {E}).M{0}{E} (MM){0}{E}
Da mesma forma, após a amostragem de três americanos, a probabilidade de estar em {E} é . Você precisa continuar multiplicando M sozinho até que a probabilidade seja pelo menos 50%(MMM){0}{E}
É preciso muito esforço para encontrar mas quando você tiver isso, é fácil obter o resultado.M
fonte