Somme des variables aléatoires exponentielles indépendantes

Pouvons-nous prouver un résultat de concentration net sur la somme des variables aléatoires exponentielles indépendantes, ie Soit des variables aléatoires indépendantes telles que . Soit . Pouvons-nous prouver des bornes de la forme . Cela suit directement si nous utilisons la forme de variance des limites de chernoff et donc je crois que c'est vrai, mais les limites que je lis nécessitent une limite ou ont une certaine dépendance sur la limite des variables. Quelqu'un pourrait-il me montrer une preuve de ce qui précède? $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 Harceler
la source

il suffit de suivre la preuve de chernoff: il est facile de délimiter le moment exponentiel des variables aléatoires exponentielles.

Sasho Nikolov

J'ai essayé de répéter la preuve de chernoff. Je l'ai fait pour le cas le plus simple où tout . Je peux obtenir le type de relation que je recherche dans une condition douce de . Une telle condition survient-elle naturellement ou est-elle due à ma mauvaise solution?

λ_{i} = λ

$\lambda_i = \lambda$

t < n λ

$t < n\lambda$

NAG

Consultez Lemma 2.8 ici eprint.iacr.org/2010/076.pdf

Sasho Nikolov

Oui, cela a du sens. Même dans leur lemme ils ont une condition sur être assez petit. Bon alors ma solution semble correcte. Merci beaucoup pour les liens et la suggestion.

t

$t$

NAG

@SureshVenkat fait. NAg, je pense qu'il y a des fautes de frappe dans votre question. Tout d'abord, est un CDF très impair pour positif . Voulez-vous dire ? Si vous l'avez fait, la variance est de la forme et votre borne chernoff ne semble pas tout à fait correcte.

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

Réponses:

Pour être concret, disons que le pdf du rv est $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|}.$

Il s'agit de la distribution de Laplace, ou la double distribution exponentielle. Sa variance est . Le cdf est $\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}$ pour .

x \geq 0

$x \geq 0$

La fonction de génération de moment de est $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},$ pour . En utilisant ce fait et la méthode des moments exponentiels qui est standard dans la preuve des bornes de Chernoff, vous obtenez que pour et , l'inégalité suivante tient

| 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},$

tant que . Vous pouvez trouver une dérivation détaillée dans la preuve du lemme 2.8 de cet article .

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

$t \leq 2\sigma \min_{i}{\lambda_i}$

Sasho Nikolov
la source

Merci beaucoup pour la réponse. Cependant, dans mon application, il n'est pas nécessairement vrai que . Cependant, on s'attendrait à une concentration encore plus forte dans le cas . Nous pouvons obtenir un tel résultat si nous n'utilisons pas l'approximation de qui restreint la plage de dans la preuve mais l'analyse de cela devient ingérable dans le cas de différent . Des suggestions à ce sujet?

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

cela va être une agitation vigoureuse de la main, mais je m'attends à ce que de si grandes valeurs de soient plus susceptibles de se produire lorsque seul un petit nombre de dépasse la médiane depar beaucoup. mais les doubles variables exponentielles ont une queue plus lourde que les gaussiens, et un petit nombre d'entre elles ne peuvent pas se concentrer aussi étroitement

X

$X$

X_{i}

$X_i$

| X_{i} |

$|X_i|$

Sasho Nikolov

Je me rends compte que ce que j'ai écrit ci-dessus n'est pas clair: je m'attends à ce que cette sortie dans la queue ressemble à la queue d'un autre rv qui est la somme d'un petit nombre de double rv exponentielle La queue de ce ne devrait pas être sous-gaussien.

X

$X$

X^{'}

$X'$

X^{'}

$X'$

Sasho Nikolov

Pour la distribution Laplace, si vous utilisez la borne de Bernoulli, vous pouvez écrire

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},$ où . Ensuite, la méthode classique de Chernoff donne

σ^{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}} .$

Notez que ces limites sont valables pour les valeurs illimitées de et . Les limites à droite montrent les deux régimes possibles. Pour les petites valeurs de nous obtenons une concentration «normale» , tandis que pour les grandes valeurs de nous obtenons , qui est également le CDF pour une seule variable distribuée Laplace. $t$ $\lambda_i$ $t$ $e^{-t^2/2}$ $t$ $\approx e^{-\sqrt{2}t}$

La borne vous permet d'interpoler entre les deux situations, mais je soupçonne que dans presque tous les cas, on sera fermement dans le grand ou le petit . $1-\sqrt{1+2t^2}$ $t$ $t$

Pour la distribution exponentielle, les mêmes techniques nous donnent où . D'où Donc, vous obtenez toujours quelque chose d' assez normal, mais avec plutôt que comme nous aurions pu l'espérer. Je ne sais pas s'il est possible d'obtenir une limite en termes de variance. Vous pouvez essayer d'étudier , mais cela ne semble pas être facile à travailler. $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
la source

Je n'ai pas le temps de travailler sur les détails mais je suis sûr à 99,9% que l'on peut obtenir une limite pour les variables aléatoires distribuées de façon exponentielle qui dépend de la variance. Votre fonction de génération du moment semble excessivement lâche.

Warren Schudy

@Warren Schudy, quelle serait votre approche?

Thomas Ahle

Je vois deux approches évidentes: 1. La deuxième borne répertoriée sur en.wikipedia.org/wiki/… semble que cela devrait fonctionner. 2. Trouvez une limite plus stricte sur la fonction de génération de moment.

Warren Schudy

@WarrenSchudy La borne de Bernstein donne , mais uniquement pour . Je suppose que cela est similaire à la réponse 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

Il est inévitable que les limites de style gaussien s'arrêtent à un moment donné. Même une seule variable aléatoire exponentiellement distribuée a finalement des queues plus grasses que n'importe quelle gaussienne.

Warren Schudy