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:
- A declaração deve ser razoavelmente conhecida (o tipo de coisa que seria ensinada em algum tipo de aula de pós-graduação)
- Deveria haver uma prova "padrão" disponível em livros didáticos ou material de referência padrão ensinado "comumente"
- 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.
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
-
- 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.
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.Σp2 ∃ ∀ ∃ ∀
fonte
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 σ=∥a∥2 t≥2
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 gaussianorj 0 1 Xi Gi rj 0 rj 1 termo a termo domina o caso Bernoulli. Portanto,
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 2 ⋅ t ! / ( 2 t / 2 ⋅ ( t / 2 ) ! ) (Aproximadamente " a " t 2 t t /2 ∑i|ai|Gi ∥a∥2 t ∥a∥t2⋅t!/(2t/2⋅(t/2)!) ); isso é conhecido como desigualdade de Khintchine. Então,∥a∥t2tt/2
Set t = λ 2 / ( C ⋅ ‖ uma ‖ 2 2 ) para um suficientemente grande constante C e você começa a cauda Gaussian limite e x
fonte
fonte