Soma das variáveis ​​aleatórias exponenciais independentes

12

Podemos provar um resultado nítido de concentração na soma de variáveis ​​aleatórias exponenciais independentes, ou seja, Seja variáveis ​​variáveis ​​aleatórias independentes, de modo que . Seja . Podemos provar limites da forma . Isso segue diretamente se usarmos a forma de variação dos limites de chernoff e, portanto, acredito que seja verdade, mas os limites que leio requerem limites ou dependem do limite das variáveis. Alguém poderia me apontar uma prova do exposto? P r ( X i < x ) = 1 - e - x / λ i Z = X i P r ( | Z - μ Z | > t ) < e - t 2 /( λ i ) 2X1,XrPr(Xi<x)=1ex/λiZ=XiPr(|ZμZ|>t)<et2/(λi)2

NAg
fonte
basta seguir a prova de chernoff: é fácil limitar o momento exponencial das variáveis ​​aleatórias exponenciais.
Sasho Nikolov
Eu tentei repetir a prova de chernoff. Fiz isso no caso mais simples quando all . Posso obter o tipo de relação que estou procurando sob uma condição moderada de . Essa condição surge naturalmente ou é devido à minha solução não tão boa? t < n λλi=λt<nλ
Nag
3
Verifique o Lema 2.8 aqui eprint.iacr.org/2010/076.pdf
Sasho Nikolov
Sim, isso faz sentido. Mesmo no lema, eles têm uma condição de serem suficientemente pequenos. Ok, então minha solução parece correta. Muito obrigado pelos links e pela sugestão. t
Nag
1
@SureshVenkat done. Não, acho que existem alguns erros de digitação em sua pergunta. Primeiro, é um CDF muito estranho para positivo . Você quis dizer ? Se você fez, a variação é da forma e seu limite de chernoff não parece muito correto. Pr[Xi<x]=eλixPr [ X i < x ] = 1 - e - λ i x λ - 2 ixPr[Xi<x]=1eλixλi2
Sasho Nikolov 02/07/2013

Respostas:

7

Por concretude, diga que o pdf do rv éXi

p(Xi=x)=12λieλi|x|.

Esta é a distribuição de Laplace ou a distribuição exponencial dupla. Sua variação é . O cdf é2λi2

Pr[Xix]=112eλix
para .x0

A função geradora de momento de éXi

E euXi=11u2/λi2,
| u| <ΛiX=ΣiXiσ2=2Σiλ - 2 i para . Usando esse fato e o método do momento exponencial que é padrão na prova dos limites de Chernoff, você obtém o resultado para e , a seguinte desigualdade é válida|u|<λiX=iXiσ2=2iλi2

Pr[X>tσ]<et2/4,
t 2 σ min i λ i contanto que . Você pode encontrar uma derivação detalhada na prova do Lema 2.8 deste documento .t2σminiλi

Sasho Nikolov
fonte
Muito obrigado pela resposta. No entanto, no meu aplicativo, não é necessariamente verdade que . No entanto, seria de esperar uma concentração ainda mais forte no caso . Podemos obter esse resultado se não usarmos a aproximação de que restringe o intervalo de na prova, mas a análise disso se torna incontrolável no caso de diferente . Alguma sugestão nessa frente? t>t2σminiλi1/(1-x)e c x tλi st>2σminiλi1/(1x)ecxtλis
Nag
isso vai ser um aceno de mão vigoroso, mas espero que esses valores grandes de provavelmente ocorram quando apenas um pequeno número de exceder a mediana depor muito. mas variáveis exponenciais duplos têm uma cauda mais pesado do que gaussianas, e um pequeno número deles não pode concentrar-se que com forçaX i | X i |XXi|Xi|
Sasho Nikolov
2
Estou percebendo que o que escrevi acima não é claro: espero que, assim, na cauda pareça com a cauda de outro rv que é a soma de um pequeno número de rv exponencial duplo A cauda de tal não deve ser sub-gaussiano. X X XXX
Sasho Nikolov
3

Para a distribuição Laplace, se você usar o Bernoulli, poderá escrever

σ2=2Σiλ - 2 i

EeuiXi=i11u2/λi211u2σ2/2,
que . Então o método clássico de Chernoff para darσ2=2iλi2

Pr[iXitσ]1+1+2t22e11+2t2{(et/2+1)e2tet2/2+t4/8.

Note-se que estes limites segure por valores irrestritos de e . Os limites à direita mostram os dois regimes possíveis. Para valores pequenos de , obtemos concentração `normal ' , enquanto que para valores grandes de obtemos , que também é o CDF para uma única variável distribuída Laplace.λ i t e - t 2 / 2 t e - tλitet2/2te2t

O limite permite que você interpole entre as duas situações, mas suspeito que, em quase todos os casos, um esteja firmemente no campo grande ou no pequeno . tt11+2t2tt

Para a distribuição exponencial, as mesmas técnicas nos fornecem que . Portanto Portanto, você ainda tem algo um pouco normal, mas com vez de como poderíamos esperar. Não sei se é possível obter um limite em termos de variação. Você pode tentar estudar , mas não parece fácil trabalhar com isso.EeuiXi11uμμ=i1/λi

Pr[(iXi)μtμ](t+1)etet2/2+t3/3.
tμtσEeu(Xiμ)2
Thomas Ahle
fonte
Não tenho tempo para descobrir os detalhes, mas tenho 99,9% de certeza de que é possível obter um limite para variáveis ​​aleatórias distribuídas exponencialmente que dependem da variação. Sua ligação com a função de geração de momentos parece excessivamente frouxa.
Warren Schudy
@ Warren Schudy, qual seria sua abordagem?
Thomas Ahle
Duas abordagens óbvias que eu vejo: 1. O segundo limite listado em en.wikipedia.org/wiki/… parece que deve funcionar. 2. Encontre um limite mais apertado na função de geração de momento.
Warren Schudy
@WarrenSchudy O limite de Bernstein fornece , mas apenas para . Suponho que isso seja semelhante à resposta de Sasho. t σ min i λ i / 2Pr[iXitσ]et2/2tσminiλi/2
Thomas Ahle 02/09
É inevitável que os limites no estilo gaussiano parem em algum momento. Mesmo uma única variável aleatória distribuída exponencialmente tem caudas mais gordas do que qualquer gaussiana.
Warren Schudy