-
Notifications
You must be signed in to change notification settings - Fork 0
/
the-sum-of-n-uniform-01-random-variables.html
235 lines (223 loc) · 11.6 KB
/
the-sum-of-n-uniform-01-random-variables.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
<!DOCTYPE html>
<html lang="en">
<head>
<title>The sum of n uniform [0,1] random variables - You don't need to prove this</title>
<link href="https://newptcai.github.io/feeds/all.atom.xml" type="application/atom+xml" rel="alternate" title="You don't need to prove this Full Atom Feed" />
<!-- CSS -->
<link rel="stylesheet" type="text/css" href="https://newptcai.github.io/theme/css/w3.css">
<link rel="stylesheet" type="text/css" href="https://newptcai.github.io/theme/css/style.css">
<link rel="stylesheet" type="text/css" href="https://newptcai.github.io/theme/css/jqcloud.css">
<link rel="stylesheet" type="text/css" href="https://newptcai.github.io/theme/css/all.min.css">
<link rel="stylesheet" type="text/css" href="https://newptcai.github.io/theme/css/shariff.min.css">
<link rel="stylesheet" type="text/css" href="https://newptcai.github.io/theme/css/pygments-highlight-github.css">
<!-- JavaScript -->
<script src="https://newptcai.github.io/theme/js/jquery-3.5.1.min.js"></script>
<script src="https://newptcai.github.io/theme/js/jqcloud.min.js"></script>
<!-- Meta -->
<meta charset="utf-8" />
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<meta name="HandheldFriendly" content="True" />
<meta name="author" content="Xing Shi Cai" />
<meta name="description" content="Update: Svante Janson told me yesterday that the integral I had at the end of this post is known as …" />
<meta name="keywords" content="probability">
<!-- Facebook OpenGraph -->
<meta property="og:site_name" content="You don't need to prove this">
<meta property="og:title" content="The sum of n uniform [0,1] random variables - You don't need to prove this" />
<meta property="og:description" content="Update: Svante Janson told me yesterday that the integral I had at the end of this post is known as …" />
<meta property="og:image" content="https://newptcai.github.io">
<meta property="og:type" content="article" />
<meta property="og:url" content="https://newptcai.github.io/the-sum-of-n-uniform-01-random-variables.html" />
<meta property="og:locale" content="de_DE" />
<meta property="og:locale:alternate" content="en_US" />
<!-- Twitter -->
<meta name="twitter:card" content="summary_large_image">
<meta name="twitter:title" content="The sum of n uniform [0,1] random variables - You don't need to prove this">
<meta name="twitter:description" content="Update: Svante Janson told me yesterday that the integral I had at the end of this post is known as …">
<meta name="twitter:image" content="https://newptcai.github.io">
</head>
<body>
<div class="w3-row w3-card w3-white">
<header id=banner>
<!-- AUTHOR INITIALS-->
<a href="https://newptcai.github.io" id=logo title="Home">XS</a>
<nav id="menu">
<ul>
<li><a href="https://newptcai.github.io/pages/research.html">Research</a></li>
<li><a href="https://newptcai.github.io/pages/teaching.html">Teaching</a></li>
<li class="active"><a href="https://newptcai.github.io/category/math.html">math</a></li>
<li ><a href="https://newptcai.github.io/category/mumble.html">mumble</a></li>
<li ><a href="https://newptcai.github.io/category/photo.html">photo</a></li>
</ul>
</nav>
</header>
</div>
<br>
<article>
<header class="w3-container col-main">
<h1>The sum of n uniform [0,1] random variables</h1>
<div class="post-info">
<div class="w3-opacity w3-margin-right w3-margin-bottom" style="flex-grow: 1;">
<span> Posted on Wed 09 January 2019 in <a href="https://newptcai.github.io/category/math.html" style="font-style: italic">math</a>
</span>
</div>
<div id="article-tags">
<span class="w3-tag w3-light-grey w3-text-red w3-hover-red">
<a href="https://newptcai.github.io/tag/probability.html" title=" All posts about Probability
">#probability</a>
</span>
</div>
</div>
</header>
<br>
<div class="col-main w3-container">
<main id="article-content">
<p>Update: Svante Janson told me yesterday that the integral I had at the end of this post is
known as the beta integral, see 5.14.1 of <em>NIST Handbook of Mathematical Functions, 2019 ed</em>.</p>
<p>What is the size of the green triangle in the following picture? Of course it is <span class="math">\(1/2\)</span>. Everybody
knows.</p>
<p><img alt="Two dimensional polyhedron \(S_2\)" src="https://newptcai.github.io/images/2019-01-09-polyhedron/2d.png">
What about this polyhedron?
<img alt="Three dimensional polyhedron \(S_3\)" src="https://newptcai.github.io/images/2019-01-09-polyhedron/3d.png">
If you still remember a bit Euclidean geometry, then you will see this is
<span class="math">\(\frac{1}{6}=\frac{1}{2}\frac{1}{3}\)</span>. Do you see where I am going?</p>
<p>Let's define an <span class="math">\(n\)</span>-dimension polyhedron
</p>
<div class="math">$$
S_n = \{(x_1,\dots,x_n) \in \mathbb R^n:1>x_1>0,\dots, 1>x_n>0, 1>x_1+\dots+x_n\}.
$$</div>
<p>
Then the previous two pictures are just <span class="math">\(S_2\)</span> and <span class="math">\(S_3\)</span>.
If you compute the volume of <span class="math">\(S_n\)</span>, you will see
</p>
<div class="math">$$
\mathrm{vol}(S_n)=
\int_{(x_1,\dots,x_n) \in S_n} \mathrm{d}(x_1,\dots,x_n)
=\frac{1}{n!}
.
$$</div>
<p>There is another way to view this.
Let <span class="math">\(U_1,\dots,U_n\)</span> be <span class="math">\(n\)</span> independent uniform random variables on <span class="math">\([0,1]\)</span>, what is the probability
that <span class="math">\(U_1+U_2 \dots U_n \le 1\)</span>? It is precise the volume of <span class="math">\(S_n\)</span> and is thus <span class="math">\(1/n!\)</span>.</p>
<p>Can we get this without doing the integral? Yes. We have
</p>
<div class="math">$$
\mathbb P\{U_1+U_2 \dots U_n \le 1\}
=
\mathbb P\{U_1+U_2 \dots U_{n-1} \le 1-U_n\}
=
\mathbb P\{U_1+U_2 \dots U_{n-1} \le U_n'\}
$$</div>
<p>
where <span class="math">\(U_n'\)</span> is again an independent uniform <span class="math">\([0,1]\)</span> random variable.
For the event <span class="math">\(U_1+U_2 \dots U_{n-1} \le U_n'\)</span> to happen, we need that <span class="math">\(U_n'\)</span> is the maximum one
among the <span class="math">\(n\)</span> variables, which has probability <span class="math">\(1/n\)</span>. Conditioning on this, <span class="math">\(U_1,\dots,U_{n-1}\)</span> are
independent and uniformly distributed on <span class="math">\([1,U_n']\)</span>. So the conditional probably of <span class="math">\(U_1+U_2 \dots
U_{n-1} \le U_n'\)</span> is <span class="math">\(1/(n-1)!\)</span> by induction. Put it together, we have
</p>
<div class="math">$$
\mathbb P\{U_1+U_2 \dots U_n \le 1\}
=
\mathbb P\{U_1+U_2 \dots U_{n-1} \le U_n'|\text{$U_n'$ is the maximum}\}
\mathbb P\{\text{$U_n'$ is the maximum}\}
=
\frac{1}{n!}.
$$</div>
<p>Why do I bring up this? A few days ago, I found the following identity
</p>
<div class="math">$$
\int_{(x_1,\dots,x_n) \in S_n}
(x_1 \dots x_n)^{-1/k}
\mathrm{d}(x_1,\dots,x_n)
=
\Gamma\left(\frac{k-1}{k}\right)^n \Gamma(1+n-n/k)^{-1}
,
\qquad
k \ge 2.
$$</div>
<p>
Let <span class="math">\(k \to \infty\)</span>, then we get back our <span class="math">\(1/n!\)</span>. Does this have a probabilistic explanation?
I do not know. Maybe you know?</p>
<script type="text/javascript">if (!document.getElementById('mathjaxscript_pelican_#%@#$@#')) {
var align = "center",
indent = "0em",
linebreak = "false";
if (false) {
align = (screen.width < 768) ? "left" : align;
indent = (screen.width < 768) ? "0em" : indent;
linebreak = (screen.width < 768) ? 'true' : linebreak;
}
var mathjaxscript = document.createElement('script');
mathjaxscript.id = 'mathjaxscript_pelican_#%@#$@#';
mathjaxscript.type = 'text/javascript';
mathjaxscript.src = 'https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.3/latest.js?config=TeX-AMS-MML_HTMLorMML';
var configscript = document.createElement('script');
configscript.type = 'text/x-mathjax-config';
configscript[(window.opera ? "innerHTML" : "text")] =
"MathJax.Hub.Config({" +
" config: ['MMLorHTML.js']," +
" TeX: { extensions: ['AMSmath.js','AMSsymbols.js','noErrors.js','noUndefined.js'], equationNumbers: { autoNumber: 'none' } }," +
" jax: ['input/TeX','input/MathML','output/HTML-CSS']," +
" extensions: ['tex2jax.js','mml2jax.js','MathMenu.js','MathZoom.js']," +
" displayAlign: '"+ align +"'," +
" displayIndent: '"+ indent +"'," +
" showMathMenu: true," +
" messageStyle: 'normal'," +
" tex2jax: { " +
" inlineMath: [ ['\\\\(','\\\\)'] ], " +
" displayMath: [ ['$$','$$'] ]," +
" processEscapes: true," +
" preview: 'TeX'," +
" }, " +
" 'HTML-CSS': { " +
" availableFonts: ['STIX', 'TeX']," +
" preferredFont: 'STIX'," +
" styles: { '.MathJax_Display, .MathJax .mo, .MathJax .mi, .MathJax .mn': {color: 'inherit ! important'} }," +
" linebreaks: { automatic: "+ linebreak +", width: '90% container' }," +
" }, " +
"}); " +
"if ('default' !== 'default') {" +
"MathJax.Hub.Register.StartupHook('HTML-CSS Jax Ready',function () {" +
"var VARIANT = MathJax.OutputJax['HTML-CSS'].FONTDATA.VARIANT;" +
"VARIANT['normal'].fonts.unshift('MathJax_default');" +
"VARIANT['bold'].fonts.unshift('MathJax_default-bold');" +
"VARIANT['italic'].fonts.unshift('MathJax_default-italic');" +
"VARIANT['-tex-mathit'].fonts.unshift('MathJax_default-italic');" +
"});" +
"MathJax.Hub.Register.StartupHook('SVG Jax Ready',function () {" +
"var VARIANT = MathJax.OutputJax.SVG.FONTDATA.VARIANT;" +
"VARIANT['normal'].fonts.unshift('MathJax_default');" +
"VARIANT['bold'].fonts.unshift('MathJax_default-bold');" +
"VARIANT['italic'].fonts.unshift('MathJax_default-italic');" +
"VARIANT['-tex-mathit'].fonts.unshift('MathJax_default-italic');" +
"});" +
"}";
(document.body || document.getElementsByTagName('head')[0]).appendChild(configscript);
(document.body || document.getElementsByTagName('head')[0]).appendChild(mathjaxscript);
}
</script>
</main>
<br>
<footer>
<div class="adjust-width">
<div id="author-block" class="w3-light-grey w3-border">
<img style="width: 35px; height: 56px; margin-left:50px;" src="https://newptcai.github.io/theme/images/bookmark-red.png" alt="bookmark"></img>
<div id="author-info">
<a href="https://newptcai.github.io/authors.html#xing-shi-cai"><img
style="width: 60px; height: 60px;" src="https://newptcai.github.io/authors/xing-shi-cai.png" onerror="this.src='https://newptcai.github.io/theme/images/avatar.png'"></img>
</a>
<div style="margin-left: 20px; margin-top: 15px;">
<a href="https://newptcai.github.io/authors.html#xing-shi-cai"><span id="author-name" class="w3-hover-text-dark-grey">Xing Shi Cai</span></a>
<p id="author-story" style="max-width: 500px;"></p>
</div>
</div>
</div>
</div>
<br>
</footer>
</div>
</article>
<br>
<script src="https://newptcai.github.io/theme/js/shariff.min.js"></script>
</body>
</html>