Jumlah Variabel Acak Eksponensial Independen

Bisakah kita membuktikan hasil konsentrasi yang tajam pada jumlah variabel acak eksponensial independen, yaitu Let $X_1, \ldots X_r$ be variabel acak independen sehingga $Pr(X_i < x) = 1 - e^{-x/\lambda_i}$ . Mari $Z = \sum X_i$ . Bisakah kita membuktikan batas bentuk $Pr(|Z-\mu_Z|>t) < e^{-t^2/\sum (\lambda_i)^2}$ . Ini mengikuti secara langsung jika kita menggunakan bentuk varians dari batas-batas chernoff dan karenanya saya percaya itu benar, tetapi batas-batas yang saya baca memerlukan terikat-ness atau memiliki beberapa ketergantungan pada terikat-ness dari variabel. Bisakah seseorang menunjuk saya ke bukti di atas?

pr.probability randomness chernoff-bound Mengomel
sumber

cukup ikuti bukti chernoff: mudah untuk mengikat momen eksponensial dari variabel acak eksponensial.

Sasho Nikolov

Saya telah mencoba mengulangi bukti chernoff. Saya melakukannya untuk kasus yang lebih sederhana ketika semua

λ_{i} = λ

$\lambda_i = \lambda$ . Saya bisa mendapatkan jenis hubungan yang saya cari dalam kondisi ringan

t < n λ

$t < n\lambda$ . Apakah kondisi seperti itu muncul secara alami atau itu karena solusi saya yang tidak begitu baik?

Tidak

Periksa Lemma 2.8 di sini eprint.iacr.org/2010/076.pdf

Sasho Nikolov

Ya ini masuk akal. Bahkan di lemma mereka mereka memiliki kondisi pada

menjadi cukup kecil. Oke maka solusi saya tampaknya benar. Terima kasih banyak atas tautan dan sarannya.

t

$t$

Tidak

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

Jawaban:

Untuk konkret, katakan bahwa pdf dari rv adalah $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|}.$

Ini adalah distribusi Laplace, atau distribusi eksponensial ganda. Perbedaannya adalah . Cdf adalah $\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}$ untuk .

x \geq 0

$x \geq 0$

Fungsi penghasil momen adalah $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},$ untuk . Menggunakan fakta ini dan metode momen eksponensial yang merupakan standar dalam bukti batas Chernoff, Anda mendapatkan bahwa untuk dan , ketidaksetaraan berikut berlaku

| 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},$ selama . Anda dapat menemukan derivasi terperinci dalam bukti Lemma 2.8 dari makalah ini .

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

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

Sasho Nikolov
sumber

Terima kasih banyak atas jawabannya. Namun dalam aplikasi saya tidak selalu benar bahwa . Namun orang akan mengharapkan konsentrasi yang lebih kuat jika . Kita bisa mendapatkan hasil seperti itu jika kita tidak menggunakan perkiraan yang membatasi rentang dalam bukti tetapi analisis itu menjadi tidak terkelola dalam kasus berbeda . Ada saran di depan itu?

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$

termasuk

ini akan menjadi beberapa kuat tangan melambai, tapi saya berharap bahwa nilai-nilai besar seperti yang paling mungkin terjadi ketika hanya kecil jumlah melebihi medianoleh banyak. tetapi variabel eksponensial ganda memiliki ekor lebih berat daripada gaussians, dan sejumlah kecil dari mereka tidak dapat berkonsentrasi dengan ketat

X

$X$

X_{i}

$X_i$

| X_{i} |

$|X_i|$

Sasho Nikolov

Saya menyadari apa yang saya tulis di atas tidak jelas: Saya berharap bahwa jalan keluar di ekor terlihat seperti ekor rv yang merupakan jumlah kecil rv eksponensial ganda. Ekor seperti seharusnya tidak sub-gaussian.

X

$X$

X^{'}

$X'$

X^{'}

$X'$

Sasho Nikolov

Untuk distribusi Laplace, jika Anda menggunakan batas Bernoulli, Anda dapat menulis

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},$ mana . Kemudian metode Chernoff klasik memberi

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

Perhatikan bahwa batas ini berlaku untuk nilai dan . Batas-batas di sebelah kanan menunjukkan dua rezim yang memungkinkan. Untuk nilai kecil kita mendapatkan konsentrasi `normal ' , sedangkan untuk nilai besar kita mendapatkan , yang juga merupakan CDF untuk satu variabel terdistribusi Laplace. $t$ $\lambda_i$ $t$ $e^{-t^2/2}$ $t$ $\approx e^{-\sqrt{2}t}$

Batas memungkinkan Anda untuk melakukan interpolasi di antara kedua situasi, tetapi saya menduga bahwa dalam hampir semua kasus seseorang akan berada di besar atau kecil . $1-\sqrt{1+2t^2}$ $t$ $t$

Untuk distribusi eksponensial, teknik yang sama memberi kita mana . Karenanya Jadi Anda masih mendapatkan sesuatu yang tampak normal, tetapi dengan daripada seperti yang mungkin kita harapkan. Saya tidak tahu apakah mungkin untuk terikat dalam hal varians. Anda dapat mencoba mempelajari , tetapi sepertinya tidak mudah untuk dikerjakan. $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
sumber

Saya tidak punya waktu untuk mengerjakan perinciannya tetapi saya 99,9% yakin bahwa seseorang dapat terikat untuk variabel acak terdistribusi eksponensial yang tergantung pada varians. Batas Anda pada fungsi menghasilkan saat terlihat sangat longgar.

Warren Schudy

@ Warren Schudy, apa pendekatan Anda?

Thomas Ahle

Dua pendekatan yang jelas saya lihat: 1. Ikatan kedua tercantum di en.wikipedia.org/wiki/… sepertinya harus bekerja. 2. Temukan ikatan yang lebih erat pada fungsi menghasilkan momen.

Warren Schudy

@ WarrenSchudy Batas Bernstein memberikan , tetapi hanya untuk . Saya kira ini mirip dengan jawaban 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

Tidak dapat dihindari bahwa batas gaya Gaussian akan berhenti di beberapa titik. Bahkan satu variabel acak yang didistribusikan secara eksponensial akhirnya memiliki ekor yang lebih gemuk daripada Gaussian manapun.

Warren Schudy