Soma das variáveis aleatórias exponenciais independentes

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? $X_1, \ldots X_r$ $Pr(X_i < x) = 1 - e^{-x/\lambda_i}$ $Z = \sum X_i$ $Pr(|Z-\mu_Z|>t) < e^{-t^2/\sum (\lambda_i)^2}$

pr.probability randomness chernoff-bound 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?

λ_{i} = λ

$\lambda_i = \lambda$

t < n λ

$t < n\lambda$

Nag

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

$t$

Nag

@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 [X_{i} < x] = e^{- λ_{i} x}

$\Pr[X_i < x] = e^{-\lambda_i x}$

x

$x$

Pr [X_{i} < x] = 1 - e^{- λ_{i} x}

$\Pr[X_i < x] = 1-e^{-\lambda_i x}$

λ_{i}^{- 2}

$\lambda_i^{-2}$

Sasho Nikolov 02/07/2013

Respostas:

Por concretude, diga que o pdf do rv é $X_i$

p (X_{i} = x) = \frac{1}{2} λ_{i} e^{- λ_{i} | x |} .

$p(X_i = x) = \frac{1}{2} \lambda_i e^{-\lambda_i|x|}.$

Esta é a distribuição de Laplace ou a distribuição exponencial dupla. Sua variação é . O cdf é $\frac{2}{\lambda_i^2}$

Pr [X_{i} \leq x] = 1 - \frac{1}{2} e^{- λ_{i} x}

$\Pr[X_i \leq x] = 1 - \frac{1}{2}e^{-\lambda_i x}$ para .

x \geq 0

$x \geq 0$

A função geradora de momento de é $X_i$

E e^{u X_{i}} = \frac{1}{1 - u^{2} / λ_{i}^{2}},

$\mathbf{E}\ e^{uX_i} = \frac{1}{1 - u^2/\lambda_i^2},$

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 | < λ_{i}

$|u| < \lambda_i$

X = \sum_{i} X_{i}

$X = \sum_i X_i$

σ^{2} = 2 \sum_{i} λ_{i}^{- 2}

$\sigma^2 = 2\sum_i \lambda_i^{-2}$

Pr [X > t σ] < e^{- t^{2} / 4},

$\Pr[X > t\sigma] < e^{-t^2/4},$

contanto que . Você pode encontrar uma derivação detalhada na prova do Lema 2.8 deste documento .

t \leq 2 σ min_{i} λ_{i}

$t \leq 2\sigma \min_{i}{\lambda_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 \leq \sqrt{2} σ m i n_{i} λ_{i}

$t \leq \sqrt{2} \sigma min_i \lambda _i$

t > \sqrt{2} σ m i n_{i} λ_{i}

$t > \sqrt{2} \sigma min_i \lambda _i$

1 / (1 - x) \leq e^{c x}

$1/(1-x) \leq e^{cx}$

t

$t$

λ_{i}^{'} s

$\lambda _i 's$

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ça

X

$X$

X_{i}

$X_i$

| X_{i} |

$|X_i|$

Sasho Nikolov

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$

X^{'}

$X'$

X^{'}

$X'$

Sasho Nikolov

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

E e^{u \sum_{i} X_{i}} = \prod_{i} \frac{1}{1 - u^{2} / λ_{i}^{2}} \leq \frac{1}{1 - u^{2} σ^{2} / 2},

$Ee^{u\sum_i X_i} = \prod_i \frac1{1-u^2/\lambda_i^2} \le \frac1{1-u^2\sigma^2/2},$ que . Então o método clássico de Chernoff para dar

σ^{2} = 2 \sum_{i} λ_{i}^{- 2}

$\sigma^2=2\sum_i\lambda_i^{-2}$

Pr [\sum_{i} X_{i} \geq t σ] \leq \frac{1 + \sqrt{1 + 2 t^{2}}}{2} e^{1 - \sqrt{1 + 2 t^{2}}} \leq {\begin{cases} (e t / \sqrt{2} + 1) e^{- \sqrt{2} t} \\ e^{- t^{2} / 2 + t^{4} / 8} \end{cases} .

$\Pr[\sum_i X_i \ge t\sigma]\le \tfrac{1+\sqrt{1+2t^2}}{2} e^{1-\sqrt{1+2t^2}} \le\cases{ (et/\sqrt2+1) e^{-\sqrt{2}t} \\ e^{-t^2/2 + t^4/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. $t$ $\lambda_i$ $t$ $e^{-t^2/2}$ $t$ $\approx e^{-\sqrt{2}t}$

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 . $1-\sqrt{1+2t^2}$ $t$ $t$

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. $Ee^{u\sum_iX_i}\le\frac{1}{1-u\mu}$ $\mu=\sum_i 1/\lambda_i$

Pr [(\sum_{i} X_{i}) - μ \geq t μ] \leq (t + 1) e^{- t} \leq e^{- t^{2} / 2 + t^{3} / 3} .

$\Pr[(\sum_i X_i)-\mu \ge t\mu]\le (t+1) e^{-t} \le e^{-t^2/2+t^3/3}.$

t μ

$t\mu$

t σ

$t\sigma$

E e^{u (\sum X_{i} - μ)^{2}}

$Ee^{u(\sum X_i-\mu)^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.

Pr [\sum_{i} X_{i} \geq t σ] \leq e^{- t^{2} / 2}

$\Pr[\sum_iX_i\ge t\sigma]\le e^{-t^2/2}$

t \leq σ min_{i} λ_{i} / 2

$t\le\sigma\min_i\lambda_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

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

Respostas:

Soma das variáveis aleatórias exponenciais independentes