Perguntas na teoria da probabilidade
Embora tenha passado em alguns cursos sobre teoria das probabilidades, tanto no ensino médio quanto na universidade, tenho dificuldade em ler os artigos da TCS quando se trata de probabilidade. Parece que os autores dos trabalhos do TCS estão muito familiarizados com a probabilidade. Eles...
Existe um limite reverso de Chernoff que limita que a probabilidade de cauda seja pelo menos tanta. ou seja, se são variáveis aleatórias binomiais independentes e . Então podemos provar para alguma função .X1,X2,…,XnX1,X2,…,XnX_1,X_2,\ldots,X_nμ=E[∑ni=1Xi]μ=E[∑i=1nXi]\mu=\mathbb{E}[\sum_{i=1}^n...
É sabido que uma caminhada aleatória na grade bidimensional retornará à origem com probabilidade 1. Também é sabido que a mesma caminhada aleatória em TRÊS dimensões tem uma probabilidade estritamente menor que 1 de retornar à origem . Minha pergunta é: Existe algo no meio? Por exemplo, suponha...
Citando a Wikipedia , "[O Jogo da Vida de Conway] tem o poder de uma máquina de Turing universal: ou seja, qualquer coisa que possa ser computada algoritmicamente pode ser computada no Jogo da Vida de Conway". Esses resultados se estendem a versões barulhentas do Jogo da Vida de Conway? A versão...
O seguinte problema surgiu durante a pesquisa e é surpreendentemente limpo: Você tem uma fonte de moedas. Cada moeda tem um viés, ou seja, uma probabilidade de cair na "cabeça". Para cada moeda independentemente, existe uma probabilidade 2/3 de ter uma tendência pelo menos 0,9 e, com o resto da...
Ouvi dizer que existem argumentos heurísticos na física estatística que produzem resultados na teoria das probabilidades, para as quais provas rigorosas são desconhecidas ou muito difíceis de obter. O que é um exemplo simples de brinquedo desse fenômeno? Seria bom se a resposta assumisse pouco...
Estou interessado na densidade crítica de 3-satisfação (3-SAT) . É suposto que tal exista: se o número de cláusulas 3-SAT geradas aleatoriamente for ou mais, elas são quase certamente insatisfatórias. (Aqui é qualquer constante pequena e é o número de variáveis.) Se o número for ou menos, elas são...
É sabido que muitos parâmetros gráficos importantes mostram concentração (forte) em gráficos aleatórios, pelo menos em alguma faixa da probabilidade da aresta. Alguns exemplos típicos são: número cromático, clique máximo, conjunto independente máximo, correspondência máxima, número de domínio,...
O tempo de comutação em um gráfico conectado é definido como o número esperado de etapas em uma caminhada aleatória iniciando em , antes que o nó seja visitado e o nó seja alcançado novamente. É basicamente a soma dos dois tempos de acerto e .i j i H ( i , j ) H ( j , i )G = ( V,...
(Von Neumann deu um algoritmo que simula uma moeda justa, tendo acesso a moedas tendenciosas idênticas. O algoritmo potencialmente requer um número infinito de moedas (embora, na expectativa, finitas sejam suficientes). Essa questão diz respeito ao caso em que o número permitido de lançamentos...
Encontrei o seguinte resultado durante minha pesquisa. limn→∞E[#{|ai−aj|,1≤i,j≤m}n]=1limn→∞E[#{|ai−aj|,1≤i,j≤m}n]=1\lim\limits_{n\to \infty} \mathbb{E}\left[ \frac{\#\{|a_i-a_j|,1\le i,j\le m \}}{n} \right] = 1 onde m=ω(n−−√)m=ω(n)m=\omega(\sqrt n) e a1,⋯,ama1,⋯,ama_1,\cdots,a_m são...
Quando ensino limites de cauda, uso a progressão usual: Se seu rv for positivo, você pode aplicar a desigualdade de Markov Se você tiver independência e também variância limitada, poderá aplicar a desigualdade de Chebyshev Se cada rv independente também tiver todos os momentos limitados, você...
Se é uma função convexa, a desigualdade de Jensen indica que e mutatis mutandis quando é côncavo. Claramente, na pior das hipóteses, você não pode limitar em termos de para um convexo , mas existe um limite que segue nessa direção se é convexo, mas "não muito convexo"? Existe algum limite padrão...
Um problema clássico na teoria da probabilidade é expressar a probabilidade de um evento em termos de eventos mais específicos. No caso mais simples, pode-se dizer P[ A ∪ B ] = P[ A ] + P[ B ] - P[ A ∩ B ]P[UMA∪B]=P[UMA]+P[B]-P[UMA∩B]P[A \cup B] = P[A] + P[B] - P[A \cap B] . Vamos escrever A...
Eu pensei sobre esse problema há muito tempo, mas não tenho idéias. O algoritmo de geração é o seguinte. Assumimos que existem nós distintos numerados de a . Então, para cada em , tornamos o pai do nó na árvore um nó aleatório em . Faça a iteração de cada para que o resultado seja uma árvore...
É sabido que, se você jogar n bolas em n compartimentos, é altamente provável que a bandeja mais carregada tenha . Em geral, pode-se perguntar sobre bolas em caixas. Um artigo da RANDOM 1998 de Raab e Steger explora isso com alguns detalhes, mostrando que à medida que aumenta, a probabilidade de ir...
Uma coisa que os computadores quânticos podem fazer (possivelmente apenas com apenas os circuitos quânticos BPP + com profundidade de log) é obter uma amostra aproximada da transformada de Fourier de uma função booleana em P.± 1±1 1\pm 1 Aqui e abaixo, quando falo sobre amostragem da transformada...
Considere o seguinte processo: Existem compartimentos organizados de cima para baixo. Inicialmente, cada caixa contém uma bola. Em cada passo, nósnnn escolha uma bola aleatória ebbb mova todas as bolas da bandeja que contém para a bandeja abaixo dela. Se já era o compartimento mais baixo,...
O problema de manutenção de pedidos (ou "manutenção de pedidos em uma lista") é dar suporte às operações: singleton: cria uma lista com um item, retorna um ponteiro para ele insertAfter: dado um ponteiro para um item, insere um novo item depois dele, retornando um ponteiro para o novo...
Pode-se falar da treewidth de um circuito booleano, definindo-o como o treewidth do gráfico "moralizada" em fios (vértices) obtida da seguinte forma: os fios de conexão umaumaa e bbb quando bbb é a saída de uma porta tendo umaumaa como entrada (ou vice-versa); fios de conexão umaumaa e bbb quando...