Provas que expõem uma estrutura mais profunda

35

A prova padrão do limite de Chernoff (do livro de algoritmos aleatórios ) usa as funções de desigualdade e geração de momentos de Markov, com um pouco de expansão de Taylor. Nada muito difícil, mas um tanto mecânico.

Mas existem outras provas vinculadas a Chernoff que expõem a estrutura mais profunda que conduz o resultado. Por exemplo, há uma versão teórica da informação que segue o método dos tipos, exemplificada por este artigo de Impagliazzo e Kabanets , bem como por este breve post de Sanjoy Dasgupta . Essas últimas provas são mais "intuitivas", pois fornecem uma generalização do resultado padrão, além de explicar de onde vêm os termos engraçados no expoente (é uma divergência de KL).

Quais são bons exemplos de tais coisas? Para ser mais concreto, aqui estão as regras:

  1. A declaração deve ser razoavelmente conhecida (o tipo de coisa que seria ensinada em algum tipo de aula de pós-graduação)
  2. Deveria haver uma prova "padrão" disponível em livros didáticos ou material de referência padrão ensinado "comumente"
  3. Deveria haver uma prova alternativa que não é tão conhecida, NÃO é comumente ensinada e prova uma afirmação mais geral ou vincula a afirmação a uma estrutura matemática mais profunda.

Vou começar com dois exemplos.

  1. O chernoff ligado

    • Prova "manual": desigualdade de markov, funções geradoras de momento, expansão de Taylor (RM)
    • Prova incomum e perspicaz: método dos tipos, expoente da cauda envolvendo divergência de KL
  2. O Lema de Schwartz-Zippel

    • Prova de "livro didático": caso-base envolvendo polinômio univariado. Indução no número de variáveis
    • prova "incomum": argumento geométrico via Dana Moshkovitz (e Per Vognsen )

Um exemplo por resposta, por favor.

ps Não estou implicando necessariamente que a prova incomum deva ser ensinada: uma prova direta geralmente é mais fácil para os alunos. Mas no sentido de que "provas nos ajudam a entender", essas provas alternativas são muito úteis.

Suresh Venkat
fonte

Respostas:

23

Não tenho certeza de que é exatamente isso que você está procurando, pois já vi a prova "incomum" nos livros didáticos, mas: o tempo O (n log n) com o quicksort.

  • Prova "manual": estabeleça uma relação de recorrência aleatória, prove por indução que ela possui a solução desejada.

  • Prova "incomum": encontre uma fórmula simples para a probabilidade de comparação de dois elementos (é apenas 2 / (d + 1) em que d é a diferença entre suas classificações na ordem classificada) e use linearidade de expectativa e séries harmônicas para calcular o número esperado de pares que são comparados.

A prova de livro didático exige menos insights criativos, mas a prova incomum introduz uma técnica que é muito útil em outras análises de algoritmos, por exemplo, para algoritmos incrementais aleatórios em geometria computacional.

David Eppstein
fonte
3
Eu acho que isso funciona. é um bom exemplo. você está certo de que a prova "incomum" também está nos livros didáticos, mas ainda não é tão comum.
Suresh Venkat
11
Eu ensino a estudantes de graduação essa prova "incomum" há mais de uma década.
Jeffε
Não sei o que os outros pensam disso; mas Jon Bentley fez uma análise de tempo de execução muito elegante para o tempo de execução esperado de classificação rápida no texto Beautiful Code. Você também pode acessar o vídeo dele sobre o mesmo tópico <a href=" youtube.com/watch?v=aMnn0Jq0J-E"> aqui </ a >. Tenho a certeza que esta é a "análise do livro" de tempo de execução esperado de quicksort
Akash Kumar
19

Vou jogar fora um de complexidade, a prova de que o BPP está em . A prova livro é devido a Lautemann, basta escrever o expressão e mostrar que funciona com um argumento probabilístico simples. A prova incomum: adivinhe uma função difícil ( para adivinhar, para verificar a dureza) e conecte-a ao gerador Nisan-Wigderson.Σ2p

Lance Fortnow
fonte
Além disso, a prova de Lautemann simplifica bastante a prova de Sipser (1983), que é atribuída por Sipser a Gacs.
MS Dousti 19/11/10
11
Existe uma referência para a prova "incomum" ou é folclore?
MS Dousti 19/11/10
2
A prova está no jornal Nisan-Wigderson.
precisa
2
É uma "prova incomum", tudo bem, mas qual é o "novo entendimento" dessa prova? Eu acho que a prova de Lautemann é mais esclarecedora. Estou faltando alguma coisa aqui?
V Vinay
13

Nós todos sabemos para Bernoulli ± 1 X i deve se comportar como um Gaussian com desvio padrão σ = uma 2 , certo? Então, vamos provar isso, relacionando-se diretamente com gaussianos! Tomando t 2 um número inteiro,iaiXi±1 Xiσ=a2t2

E[(iaiXi)t]=i1,,it(j=1taij)E[j=1tXij]i1,,it(j=1t|aij|)E[j=1tXij]=i1<<imr1,,rmjrj=tj rj>0(tr1,,rm)(j=1m|aij|rj)(j=1mE[Xijrj])

Agora, vejamos a soma acima à direita. Em qualquer soma solicitada, ou algum é ímpar, tornando a expectativa 0 , ou todos são pares, tornando-o 1 . Imagine substituir todo o X i pelo Gaussian G i . Então estaríamos em um cenário semelhante: odd r j daria 0 , e todos ainda r j tornaria o produto pelo menos 1 . Então, o caso gaussianorj01XiGirj0rj 1 termo a termo domina o caso Bernoulli. Portanto,

E[(iaiXi)t]E[(i|ai|Gi)t]

Mas, por -estabilidade do Gaussian, Σ i | a i | G i é em si um Gaussian com desvio padrão uma 2 , por isso sabemos seus momentos! Assim, o nosso t th momento é delimitada por uma t 2t ! / ( 2 t / 2( t / 2 ) ! ) (Aproximadamente " a " t 2 t t /2i|ai|Gia2ta2tt!/(2t/2(t/2)!) ); isso é conhecido como desigualdade de Khintchine. Então,a2ttt/2

Set t = λ 2 / ( C uma 2 2 ) para um suficientemente grande constante C e você começa a cauda Gaussian limite e x

Pr[|EuumaEuXEu|>λ]<2O(t)λ-t__uma__2ttt/2
t=λ2/(C__uma__22)C . Ouvi pela primeira vez essa prova da desigualdade de Khintchine ao conversar com Daniel Kane, mas provavelmente há uma referência mais antiga. Observe a prova também deixa claro qual o nível de independência entre os X i você precisa obter vários limites da cauda.exp(Ω(λ2/a22))Xi
Jelani Nelson
fonte
6

AriiA

i(ri!)1/ri.
Timothy Chow
fonte