1
00:00:00,520 --> 00:00:04,480
okay so today on numerical methods yes


2
00:00:04,480 --> 00:00:06,870
maybe always to give you an orientation


3
00:00:06,870 --> 00:00:11,110
we are discussing the numerical method


4
00:00:11,110 --> 00:00:14,650
called Monte Carlo method we are


5
00:00:14,650 --> 00:00:17,169
discussing how to generate other


6
00:00:17,169 --> 00:00:20,859
distributions from sequences of uniform


7
00:00:20,859 --> 00:00:28,359
distributed random drawings okay and the


8
00:00:28,359 --> 00:00:31,079
first method we discussed was the


9
00:00:31,079 --> 00:00:33,340
inversion of the distribution function


10
00:00:33,340 --> 00:00:36,640
and for that we had to actually define


11
00:00:36,640 --> 00:00:39,489
what is the inverse of the distribution


12
00:00:39,489 --> 00:00:40,809
function because the distribution


13
00:00:40,809 --> 00:00:44,859
function can be as monotone but not


14
00:00:44,859 --> 00:00:48,309
strictly monotone and for that we define


15
00:00:48,309 --> 00:00:51,879
some generalized version which you see


16
00:00:51,879 --> 00:00:54,870
here in the picture so whenever you have


17
00:00:54,870 --> 00:01:00,789
say some area of non-uniqueness like


18
00:01:00,789 --> 00:01:06,189
here we take just the infimum of this


19
00:01:06,189 --> 00:01:10,479
set huh and we could actually then show


20
00:01:10,479 --> 00:01:12,640
you have this lemma we could prove this


21
00:01:12,640 --> 00:01:16,750
lemma that if you have given the inverse


22
00:01:16,750 --> 00:01:20,229
this generalized inverse of the


23
00:01:20,229 --> 00:01:22,420
distribution function then from a


24
00:01:22,420 --> 00:01:25,540
uniform random variables or from a


25
00:01:25,540 --> 00:01:28,840
sequence of uniform drawings you can


26
00:01:28,840 --> 00:01:34,210
generate an F distributed random


27
00:01:34,210 --> 00:01:40,960
variable X now by applying the inverse


28
00:01:40,960 --> 00:01:46,149
here so now what do we do if we do not


29
00:01:46,149 --> 00:01:49,030
have the inverse of the distribution


30
00:01:49,030 --> 00:01:51,820
function so either we do not know across


31
00:01:51,820 --> 00:01:55,600
formula or we do not have a nice


32
00:01:55,600 --> 00:01:57,700
approximation like the one which we had


33
00:01:57,700 --> 00:02:00,939
for the normal distribution then here I


34
00:02:00,939 --> 00:02:02,710
would like to discuss an alternative


35
00:02:02,710 --> 00:02:04,600
method with you which is called


36
00:02:04,600 --> 00:02:07,630
acceptance rejection also quite


37
00:02:07,630 --> 00:02:09,570
interesting from the way how it is


38
00:02:09,570 --> 00:02:11,300
constructed


39
00:02:11,300 --> 00:02:15,260
and this message makes some other


40
00:02:15,260 --> 00:02:20,300
assumptions so actually first what do we


41
00:02:20,300 --> 00:02:26,500
like to do so let's take the right pen


42
00:02:26,500 --> 00:02:31,610
so what we like to do we like to


43
00:02:31,610 --> 00:02:40,010
generate a sequence generate a sequence


44
00:02:40,010 --> 00:02:43,660
let's call it X I


45
00:02:43,660 --> 00:02:53,390
and this sequence should be joins of an


46
00:02:53,390 --> 00:03:03,680
F distributed random ever say I call it


47
00:03:03,680 --> 00:03:08,600
capital X so this is what we have but


48
00:03:08,600 --> 00:03:19,360
maybe we do not know we do not know F


49
00:03:19,360 --> 00:03:31,430
okay so there is no need to know F


50
00:03:31,430 --> 00:03:35,540
inverse in this method you know or you


51
00:03:35,540 --> 00:03:41,150
even do not need to know F so what we


52
00:03:41,150 --> 00:03:45,120
need to know is


53
00:03:45,120 --> 00:03:47,310
you


54
00:03:47,310 --> 00:03:58,050
we know F prime the density record that


55
00:03:58,050 --> 00:03:59,880
this is for example the situation which


56
00:03:59,880 --> 00:04:02,400
we had for the normal distribution for


57
00:04:02,400 --> 00:04:04,590
the normal distribution density is 1


58
00:04:04,590 --> 00:04:07,019
divided by square root to P times


59
00:04:07,019 --> 00:04:10,860
exponential minus x squared half so we


60
00:04:10,860 --> 00:04:15,410
know the density nice dose formula 

61
00:04:15,410 --> 00:04:15,420
know the density nice dose formula 

62
00:04:15,420 --> 00:04:18,890
know the density nice dose formula do not know F or F inverse in closed


63
00:04:18,890 --> 00:04:18,900
do not know F or F inverse in closed


64
00:04:18,900 --> 00:04:22,650
form but then we need some additional


65
00:04:22,650 --> 00:04:24,740
stuff


66
00:04:24,740 --> 00:04:31,680
actually we know we need to know how to


67
00:04:31,680 --> 00:04:41,930
generate some utility sequence a


68
00:04:41,930 --> 00:04:52,229
sequence Y I and these are toys over GE


69
00:04:52,229 --> 00:04:58,680
distributed


70
00:04:58,680 --> 00:05:02,360
the Bible


71
00:05:02,360 --> 00:05:06,060
why so we need some other sequence and


72
00:05:06,060 --> 00:05:08,510
this sequence should have a relation to


73
00:05:08,510 --> 00:05:15,480
our function f or f time yeah we know


74
00:05:15,480 --> 00:05:20,620
that is a constant C such that the


75
00:05:20,620 --> 00:05:26,260
so a constant C such that C times the


76
00:05:26,260 --> 00:05:30,730
density of G is larger than the density


77
00:05:30,730 --> 00:05:35,460
of F so if you draw the two densities


78
00:05:35,460 --> 00:05:39,880
the density of G should be above F if


79
00:05:39,880 --> 00:05:42,220
there is a if there is some region where


80
00:05:42,220 --> 00:05:44,350
it is not above it's maybe not a problem


81
00:05:44,350 --> 00:05:46,840
you can you can multiply it with the C


82
00:05:46,840 --> 00:05:49,990
and shift it a little bit up as long as


83
00:05:49,990 --> 00:05:56,590
this region has nonzero values so we


84
00:05:56,590 --> 00:06:00,250
have this clique with the constant you


85
00:06:00,250 --> 00:06:02,200
know we can use but actually we need


86
00:06:02,200 --> 00:06:04,230
somehow the property that the density of


87
00:06:04,230 --> 00:06:11,620
G lies above F most importantly in the


88
00:06:11,620 --> 00:06:15,460
azan to asymptotics yeah so f decays


89
00:06:15,460 --> 00:06:19,000
faster than g so if you have something


90
00:06:19,000 --> 00:06:20,530
like this and this is maybe not a very


91
00:06:20,530 --> 00:06:22,720
strong assumption yeah so for maybe


92
00:06:22,720 --> 00:06:25,480
exponential distributed random variable


93
00:06:25,480 --> 00:06:27,400
exponential minus x squared


94
00:06:27,400 --> 00:06:30,670
you know I immediately have exponential


95
00:06:30,670 --> 00:06:33,940
minus X decays slower and so I could use


96
00:06:33,940 --> 00:06:35,170
an exponentially distributed random


97
00:06:35,170 --> 00:06:39,280
variable to dominate the normal


98
00:06:39,280 --> 00:06:41,350
distribution tensity in the other


99
00:06:41,350 --> 00:06:44,950
asymptotics this is our situation


100
00:06:44,950 --> 00:06:47,620
actually the third point the the


101
00:06:47,620 --> 00:06:49,000
requirement is even a little bit


102
00:06:49,000 --> 00:06:52,570
stricter I need two sequences one one


103
00:06:52,570 --> 00:06:55,510
uniform independent one but essentially


104
00:06:55,510 --> 00:06:58,240
these are now the requirements and these


105
00:06:58,240 --> 00:07:00,580
requirements are not so strong and the


106
00:07:00,580 --> 00:07:03,100
claim is that if we have this situation


107
00:07:03,100 --> 00:07:05,710
I can generate a sequence of F


108
00:07:05,710 --> 00:07:14,260
distributed random barber okay maybe I


109
00:07:14,260 --> 00:07:24,490
collect a few typos here F distributed


110
00:07:24,490 --> 00:07:34,970
so yeah this is the situation this is


111
00:07:34,970 --> 00:07:37,760
the corresponding lemma so accept


112
00:07:37,760 --> 00:07:41,270
acceptance rejection sampling let F


113
00:07:41,270 --> 00:07:45,580
denote a distribution function


114
00:07:45,580 --> 00:07:47,670
you


115
00:07:47,670 --> 00:07:49,850
for which we like to generate a sequence


116
00:07:49,850 --> 00:07:59,180
then given a sequence two-dimensional UI


117
00:07:59,180 --> 00:08:03,990
y I so this is a sequence of a


118
00:08:03,990 --> 00:08:10,820
two-dimensional vector being you Y of


119
00:08:10,820 --> 00:08:17,360
random variables U and Y where u is


120
00:08:17,360 --> 00:08:23,280
uniform distributed so U is uniform


121
00:08:23,280 --> 00:08:28,200
distributed on 0 1 and Y is the one


122
00:08:28,200 --> 00:08:30,300
which he had mentioned in the multi


123
00:08:30,300 --> 00:08:36,140
motivation the one that is G distributed


124
00:08:36,140 --> 00:08:42,769
in addition both have to be independent


125
00:08:42,769 --> 00:08:45,160
you


126
00:08:45,160 --> 00:08:48,579
okay but maybe this is not a big


127
00:08:48,579 --> 00:08:51,579
restriction here so you know that if 

128
00:08:51,579 --> 00:08:51,589
restriction here so you know that if 

129
00:08:51,589 --> 00:08:56,079
restriction here so you know that if have one uniform random sequence if it


130
00:08:56,079 --> 00:08:56,089
have one uniform random sequence if it


131
00:08:56,089 --> 00:08:58,639
is episode o number generator we can


132
00:08:58,639 --> 00:09:00,529
just generate a two-dimensional vector


133
00:09:00,529 --> 00:09:02,990
by populating the entries one by the


134
00:09:02,990 --> 00:09:06,560
other so we can generate a uniform


135
00:09:06,560 --> 00:09:08,690
distributed sequence in two dimensions


136
00:09:08,690 --> 00:09:12,800
and maybe if we can apply the inversion


137
00:09:12,800 --> 00:09:15,620
method for G we can generate from the


138
00:09:15,620 --> 00:09:18,230
second component the G and the two may


139
00:09:18,230 --> 00:09:22,430
be independent so G is K so the sequence


140
00:09:22,430 --> 00:09:26,269
YJ which is GG distributed is some kind


141
00:09:26,269 --> 00:09:29,449
of helper sequence actually we will


142
00:09:29,449 --> 00:09:32,769
single out the points from this sequence


143
00:09:32,769 --> 00:09:36,250
so now I need this assumption on the


144
00:09:36,250 --> 00:09:41,389
densities so for the density of G which


145
00:09:41,389 --> 00:09:47,209
I call little G and the density of F


146
00:09:47,209 --> 00:09:52,160
which I call a little F so maybe I check


147
00:09:52,160 --> 00:09:55,089
here the yellow


148
00:09:55,089 --> 00:09:58,180
okay for these we have the relation that


149
00:09:58,180 --> 00:10:01,540
we find a constant C such that the


150
00:10:01,540 --> 00:10:06,220
density of F is smaller than the density


151
00:10:06,220 --> 00:10:10,029
of G with some multiplied with some


152
00:10:10,029 --> 00:10:19,899
constant so some C times G of X okay


153
00:10:19,899 --> 00:10:24,339
so in in maybe I try us more picture


154
00:10:24,339 --> 00:10:27,519
here I answer if you there for example


155
00:10:27,519 --> 00:10:34,720
here a density like say which which


156
00:10:34,720 --> 00:10:37,449
color should I use yeah so maybe like


157
00:10:37,449 --> 00:10:39,970
like the normal distribution yeah so I


158
00:10:39,970 --> 00:10:42,040
have something like this the normal


159
00:10:42,040 --> 00:10:47,519
distribution which goes here oops


160
00:10:47,519 --> 00:10:51,839
like this then maybe you can find some


161
00:10:51,839 --> 00:10:55,930
distribution function G which the case


162
00:10:55,930 --> 00:11:06,069
he is slower huh so this is the G okay


163
00:11:06,069 --> 00:11:10,029
and then you just multiply with the


164
00:11:10,029 --> 00:11:12,939
constant C now to move this here a


165
00:11:12,939 --> 00:11:17,769
little bit up okay and then you have


166
00:11:17,769 --> 00:11:23,350
disc right here yeah okay so this year


167
00:11:23,350 --> 00:11:30,540
is C times G this is G


168
00:11:30,540 --> 00:11:39,070
Saji and this is D F so I need to find a


169
00:11:39,070 --> 00:11:43,570
constant C to dominate this actually


170
00:11:43,570 --> 00:11:46,270
later we will see that it's nice to have


171
00:11:46,270 --> 00:11:49,600
the smallest such constants okay so this


172
00:11:49,600 --> 00:11:51,430
is the situation which I had already


173
00:11:51,430 --> 00:11:56,260
described and then the sequence of the


174
00:11:56,260 --> 00:12:01,050
following numbers so the sequence X i


175
00:12:01,050 --> 00:12:05,800
where from Y I so Y is the sequence I


176
00:12:05,800 --> 00:12:10,690
have which is G distributed where we


177
00:12:10,690 --> 00:12:16,360
just take specific indices so we just


178
00:12:16,360 --> 00:12:21,990
take here specific indices of Y I this


179
00:12:21,990 --> 00:12:26,710
sequence is F distributed so just this


180
00:12:26,710 --> 00:12:33,830
sequence X I pairs distribution F


181
00:12:33,830 --> 00:12:40,760
and what are the specific indices so


182
00:12:40,760 --> 00:13:02,430
here it's take only specific indices so


183
00:13:02,430 --> 00:13:06,630
from the YJ so how are these calculated


184
00:13:06,630 --> 00:13:10,620
so I initialize so actually here my eye


185
00:13:10,620 --> 00:13:16,110
starts in zero so I initialize k zero to


186
00:13:16,110 --> 00:13:21,960
zero and then I take the index ki is the


187
00:13:21,960 --> 00:13:24,150
next index which is larger than the


188
00:13:24,150 --> 00:13:26,250
previous index so this is just that I


189
00:13:26,250 --> 00:13:31,200
take the next guys in the sequence for


190
00:13:31,200 --> 00:13:35,730
which actually the uniform number from


191
00:13:35,730 --> 00:13:39,920
our two-dimensional vector here is


192
00:13:39,920 --> 00:13:43,840
smaller than


193
00:13:43,840 --> 00:13:48,220
the Y the G distributed number why


194
00:13:48,220 --> 00:13:51,520
plucked into the density now


195
00:13:51,520 --> 00:13:57,220
so F of Y divided by C G of Y this


196
00:13:57,220 --> 00:13:59,710
strange expression here so actually here


197
00:13:59,710 --> 00:14:03,790
you have some test criteria and your


198
00:14:03,790 --> 00:14:06,940
test criteria if you take the number or


199
00:14:06,940 --> 00:14:07,630
not


200
00:14:07,630 --> 00:14:14,200
this is your uniform number smaller then


201
00:14:14,200 --> 00:14:16,529
what you get if you pluck the g


202
00:14:16,529 --> 00:14:19,900
distributed number in the two densities


203
00:14:19,900 --> 00:14:27,520
take the ratio and divided by C ok so


204
00:14:27,520 --> 00:14:31,089
you see that we take a few numbers from


205
00:14:31,089 --> 00:14:34,060
the sequence Y so sometimes we accept


206
00:14:34,060 --> 00:14:35,830
the number sometimes we reject the


207
00:14:35,830 --> 00:14:40,450
number and the criteria to accept or


208
00:14:40,450 --> 00:14:47,770
reject the number is this thing here so


209
00:14:47,770 --> 00:15:00,690
this is the criteria if we accept


210
00:15:00,690 --> 00:15:08,000
or rechecked


211
00:15:08,000 --> 00:15:17,040
the yj2 become a number X okay maybe a


212
00:15:17,040 --> 00:15:19,980
small illustration but I believe you


213
00:15:19,980 --> 00:15:23,250
should have the idea yeah so actually we


214
00:15:23,250 --> 00:15:28,290
need to generate two sequences you I are


215
00:15:28,290 --> 00:15:34,140
say you J and YJ so you sequence is here


216
00:15:34,140 --> 00:15:37,470
I always used Queen for you so this is


217
00:15:37,470 --> 00:15:42,839
the sequence you the two dimensional


218
00:15:42,839 --> 00:15:46,380
vector is independent this sequence you


219
00:15:46,380 --> 00:15:50,730
is uniform this sequence Y is G


220
00:15:50,730 --> 00:15:55,449
distributed so this is a G distributed


221
00:15:55,449 --> 00:16:02,670
and this one here is uniform


222
00:16:02,670 --> 00:16:06,910
then on these on this sequence you


223
00:16:06,910 --> 00:16:12,760
compare what do you get for this by


224
00:16:12,760 --> 00:16:17,350
looking at here this criteria you look


225
00:16:17,350 --> 00:16:21,280
at this criteria and you check if the


226
00:16:21,280 --> 00:16:24,850
criteria is too or false


227
00:16:24,850 --> 00:16:29,260
and so maybe here this falls maybe here


228
00:16:29,260 --> 00:16:36,600
it is true and maybe we check a few more


229
00:16:36,600 --> 00:16:42,180
yeah so you check these guys and maybe


230
00:16:42,180 --> 00:16:46,510
this one here is also false false and


231
00:16:46,510 --> 00:16:58,350
that one's maybe - okay then you take X


232
00:16:58,350 --> 00:17:04,420
you take X is equal to Y if the criteria


233
00:17:04,420 --> 00:17:11,470
is - yeah so this year was our Y so we


234
00:17:11,470 --> 00:17:15,640
take this one as the X so let's take


235
00:17:15,640 --> 00:17:20,620
this one here as the X and we take this


236
00:17:20,620 --> 00:17:24,190
one here as the X the other ones are


237
00:17:24,190 --> 00:17:25,810
skipped huh


238
00:17:25,810 --> 00:17:30,390
and this year is then the sequence X I


239
00:17:30,390 --> 00:17:36,100
know sorry there was a rejected one this


240
00:17:36,100 --> 00:17:40,390
one is taken here this one is taken huh


241
00:17:40,390 --> 00:17:45,850
and maybe one more then it's also


242
00:17:45,850 --> 00:17:50,980
accepted so if a few more points so this


243
00:17:50,980 --> 00:17:55,000
one here is also accepted so you see you


244
00:17:55,000 --> 00:17:57,010
get fewer points out of this you know


245
00:17:57,010 --> 00:18:01,690
you have to sample two times the


246
00:18:01,690 --> 00:18:03,790
sequence and then you just single out


247
00:18:03,790 --> 00:18:06,900
one point with a certain probability and


248
00:18:06,900 --> 00:18:09,730
but this one just sequences now F


249
00:18:09,730 --> 00:18:11,800
distributed this is the claim of this


250
00:18:11,800 --> 00:18:21,340
lemma okay so let's prove that this is


251
00:18:21,340 --> 00:18:24,310
an F distributed sequence and maybe


252
00:18:24,310 --> 00:18:26,530
sometime later or you can do it as an


253
00:18:26,530 --> 00:18:29,050
exercise you can maybe check it for a


254
00:18:29,050 --> 00:18:32,290
few examples I have examples some more


255
00:18:32,290 --> 00:18:36,340
examples in the in the script okay so


256
00:18:36,340 --> 00:18:42,340
let's do a proof we generate two


257
00:18:42,340 --> 00:18:49,090
sequences u and y so be here in this


258
00:18:49,090 --> 00:18:51,460
slide I do not talk about sequences I


259
00:18:51,460 --> 00:18:55,300
talk about the random variables and I I


260
00:18:55,300 --> 00:18:59,580
just show you that the random variable X


261
00:18:59,580 --> 00:19:02,290
generated by this condition has F


262
00:19:02,290 --> 00:19:05,350
distribution so the random variables are


263
00:19:05,350 --> 00:19:08,110
called you so on my slide I always had


264
00:19:08,110 --> 00:19:12,880
the queen color for the you and why you


265
00:19:12,880 --> 00:19:15,340
know so this is the random there behind


266
00:19:15,340 --> 00:19:18,840
the you sequence and the Y sequence and


267
00:19:18,840 --> 00:19:22,450
the first thing to note is that the


268
00:19:22,450 --> 00:19:25,630
probability that U is pilotless less or


269
00:19:25,630 --> 00:19:33,490
equal f of Y divided by C G of Y is just


270
00:19:33,490 --> 00:19:37,990
1 divided by C so the probability that


271
00:19:37,990 --> 00:19:44,560
we accept a point no probability that we


272
00:19:44,560 --> 00:19:47,389
accept the point


273
00:19:47,389 --> 00:19:55,629
so here we could maybe write probability


274
00:19:55,629 --> 00:20:06,799
that Y J is accepted this probability is


275
00:20:06,799 --> 00:20:11,899
here our head box our criteria this is


276
00:20:11,899 --> 00:20:18,950
the probability that U is less than F of


277
00:20:18,950 --> 00:20:24,889
Y divided by C G of Y this is the


278
00:20:24,889 --> 00:20:27,919
probability that we accept a point which


279
00:20:27,919 --> 00:20:30,440
comes standpoint for the sequence and


280
00:20:30,440 --> 00:20:35,929
this probability is 1 divided by C okay


281
00:20:35,929 --> 00:20:42,349
so this follows since well how do we do


282
00:20:42,349 --> 00:20:45,079
this so the trick which I'm using here


283
00:20:45,079 --> 00:20:48,649
is coming again later on the slide I


284
00:20:48,649 --> 00:20:51,739
have here the probability of some


285
00:20:51,739 --> 00:20:53,779
condition which depends on two random


286
00:20:53,779 --> 00:20:55,849
variables and actually the probability


287
00:20:55,849 --> 00:20:58,099
is a function which Maps a set of Omega


288
00:20:58,099 --> 00:21:02,059
you know so a set of little omegas to a


289
00:21:02,059 --> 00:21:05,450
number so which said is this this is the


290
00:21:05,450 --> 00:21:08,389
set of all omegas if you plug in the


291
00:21:08,389 --> 00:21:13,269
Omega inside the random variables yeah


292
00:21:13,269 --> 00:21:19,249
that this is 2 so actually if you write


293
00:21:19,249 --> 00:21:27,469
P of U less than F of Y divided by C G


294
00:21:27,469 --> 00:21:31,279
of Y so then actually this is just the


295
00:21:31,279 --> 00:21:34,039
short notation for I would like to have


296
00:21:34,039 --> 00:21:36,559
the probability of the set of all omegas


297
00:21:36,559 --> 00:21:39,589
for which this condition holds that is


298
00:21:39,589 --> 00:21:45,499
to say you of Omega is less than F of y


299
00:21:45,499 --> 00:21:56,100
of Omega divided by CG of y of Omega ok


300
00:21:56,100 --> 00:22:01,690
close to set now so this is the


301
00:22:01,690 --> 00:22:05,740
point-wise the evaluation of this


302
00:22:05,740 --> 00:22:10,060
condition on omega so but in terms of


303
00:22:10,060 --> 00:22:12,490
random variables you can interpret it as


304
00:22:12,490 --> 00:22:15,310
a two dimensional thing all values of


305
00:22:15,310 --> 00:22:18,850
you all possible values of Y and to get


306
00:22:18,850 --> 00:22:21,940
rid of this two-dimensional thing a nice


307
00:22:21,940 --> 00:22:24,310
trick is just to condition on one


308
00:22:24,310 --> 00:22:29,800
variable so we can first calculate the


309
00:22:29,800 --> 00:22:32,860
conditional probability given that we


310
00:22:32,860 --> 00:22:35,890
already know that Y has a certain value


311
00:22:35,890 --> 00:22:39,580
yeah so the probability that you the


312
00:22:39,580 --> 00:22:42,610
random variable U is less than this


313
00:22:42,610 --> 00:22:46,210
expression under the condition that we


314
00:22:46,210 --> 00:22:54,930
know that Y has some value little Y okay


315
00:22:54,930 --> 00:22:59,110
so if your condition you are allowed to


316
00:22:59,110 --> 00:23:01,570
use this condition here in your


317
00:23:01,570 --> 00:23:04,960
expression so I can just replace the


318
00:23:04,960 --> 00:23:07,720
capital y by the little Y so this is


319
00:23:07,720 --> 00:23:11,170
just the probability that U is less than


320
00:23:11,170 --> 00:23:13,840
this number yeah so now this is a number


321
00:23:13,840 --> 00:23:16,510
this is the set of all omegas where u of


322
00:23:16,510 --> 00:23:18,730
Omega is less than this number so this


323
00:23:18,730 --> 00:23:21,910
is like a marginal marginal thing yeah


324
00:23:21,910 --> 00:23:24,730
so this is just the one-dimensional


325
00:23:24,730 --> 00:23:26,860
projection of this tubular


326
00:23:26,860 --> 00:23:29,920
two-dimensional thing now projected


327
00:23:29,920 --> 00:23:34,240
along the line y equals little Y okay so


328
00:23:34,240 --> 00:23:42,500
but now note that U is uniform


329
00:23:42,500 --> 00:23:45,270
so this here's just the distribution


330
00:23:45,270 --> 00:23:52,830
function so this little box here is just


331
00:23:52,830 --> 00:24:05,970
the distribution function of U so the


332
00:24:05,970 --> 00:24:09,410
distribution function of U is just a


333
00:24:09,410 --> 00:24:10,560
constant


334
00:24:10,560 --> 00:24:17,910
yeah so you just have that this is just


335
00:24:17,910 --> 00:24:21,810
this upper bound value sorry the


336
00:24:21,810 --> 00:24:23,730
distribution function is a linear


337
00:24:23,730 --> 00:24:26,570
function so it's just the the 

338
00:24:26,570 --> 00:24:26,580
function so it's just the the 

339
00:24:26,580 --> 00:24:29,300
function so it's just the the itself yeah the number on the right hand


340
00:24:29,300 --> 00:24:29,310
itself yeah the number on the right hand


341
00:24:29,310 --> 00:24:31,620
side so you just have this is just f of


342
00:24:31,620 --> 00:24:35,070
Y divided by CG or fine okay


343
00:24:35,070 --> 00:24:38,100
so but actually we were interested here


344
00:24:38,100 --> 00:24:42,360
in the probability that U is less than F


345
00:24:42,360 --> 00:24:46,890
of Capital y but now since I have here


346
00:24:46,890 --> 00:24:54,330
the conditioner I can get the Joint


347
00:24:54,330 --> 00:24:56,160
Distribution by integrating the


348
00:24:56,160 --> 00:25:01,050
conditional one so this the probability


349
00:25:01,050 --> 00:25:06,140
that we are


350
00:25:06,140 --> 00:25:09,350
that you is less than equal F of Y


351
00:25:09,350 --> 00:25:14,080
divided by CG of Y is the integral of


352
00:25:14,080 --> 00:25:17,570
the conditional probability multiplied


353
00:25:17,570 --> 00:25:20,060
with the density integrated over all


354
00:25:20,060 --> 00:25:23,090
possible values of Y no so this is a


355
00:25:23,090 --> 00:25:27,680
standard trick yeah which you have you


356
00:25:27,680 --> 00:25:29,540
will but you can do you know if you like


357
00:25:29,540 --> 00:25:35,120
to do this so let's plug this in so you


358
00:25:35,120 --> 00:25:42,230
see this here is f of Y divided by C G


359
00:25:42,230 --> 00:25:46,490
of Y so this G of Y cancels here and


360
00:25:46,490 --> 00:25:56,630
what is left is just the integral of F


361
00:25:56,630 --> 00:26:01,850
of Y divided by C I integrate the


362
00:26:01,850 --> 00:26:06,620
density over the whole domain so this is


363
00:26:06,620 --> 00:26:10,030
just 1 now so it's just 1 divided by C


364
00:26:10,030 --> 00:26:13,790
ok so that was a first remark so


365
00:26:13,790 --> 00:26:19,340
actually you see that here here we wrote


366
00:26:19,340 --> 00:26:21,800
that this probability is the probability


367
00:26:21,800 --> 00:26:27,410
that we accept a point so the


368
00:26:27,410 --> 00:26:29,270
probability that we accept a point is


369
00:26:29,270 --> 00:26:31,610
actually just 1 divided by this constant


370
00:26:31,610 --> 00:26:35,960
C so we like to have this constant C to


371
00:26:35,960 --> 00:26:41,480
be as close as possible to 1 now so


372
00:26:41,480 --> 00:26:44,330
usually C is larger than 1 but we like


373
00:26:44,330 --> 00:26:51,520
to have it as close as possible to 1


374
00:26:51,520 --> 00:26:59,000
okay now let's prove the result so that


375
00:26:59,000 --> 00:27:07,690
is X the sequence X F distributed


376
00:27:07,690 --> 00:27:10,870
I will use again this trick with the


377
00:27:10,870 --> 00:27:17,230
conditioning okay so


378
00:27:17,230 --> 00:27:19,240
for the condition expectation a


379
00:27:19,240 --> 00:27:22,419
conditioner B I already mentioned this


380
00:27:22,419 --> 00:27:25,500
is the probability a intersected B


381
00:27:25,500 --> 00:27:29,110
relative to the size of the event space


382
00:27:29,110 --> 00:27:32,650
B so the probability of B and we will


383
00:27:32,650 --> 00:27:36,669
use this with actually two sets the


384
00:27:36,669 --> 00:27:40,809
probability or the set Y is smaller than


385
00:27:40,809 --> 00:27:43,540
a given constant X which is two constant


386
00:27:43,540 --> 00:27:46,570
in our distribution function and B is


387
00:27:46,570 --> 00:27:50,559
the set that we accept a point so this


388
00:27:50,559 --> 00:27:55,480
was the red box on our previous side the


389
00:27:55,480 --> 00:27:58,030
set that we accept a point so this is


390
00:27:58,030 --> 00:28:05,830
our condition so my sequence X is


391
00:28:05,830 --> 00:28:13,890
actually equal to the sequence Y


392
00:28:13,890 --> 00:28:16,900
so


393
00:28:16,900 --> 00:28:27,820
X is why if we accept the point so under


394
00:28:27,820 --> 00:28:36,360
the condition that we accept the point


395
00:28:36,360 --> 00:28:43,530
if the point is accepted


396
00:28:43,530 --> 00:28:46,160
you


397
00:28:46,160 --> 00:28:50,190
so the probability that X is below a


398
00:28:50,190 --> 00:28:52,530
little X so this is the distribution


399
00:28:52,530 --> 00:28:54,690
function so we like to calculate the


400
00:28:54,690 --> 00:28:57,480
distribution Virgie the probability that


401
00:28:57,480 --> 00:29:00,090
capital X is less or equal little X is


402
00:29:00,090 --> 00:29:02,880
the probability that y is less or equal


403
00:29:02,880 --> 00:29:06,240
little X under the condition that the


404
00:29:06,240 --> 00:29:08,910
point was accepted so where's the


405
00:29:08,910 --> 00:29:12,390
conditional probability that you so wish


406
00:29:12,390 --> 00:29:14,520
to condition the condition that u is


407
00:29:14,520 --> 00:29:18,180
less than f of Y divided by CG of Y so


408
00:29:18,180 --> 00:29:20,970
now these are here my two sets the


409
00:29:20,970 --> 00:29:23,220
yellow one and the red one and now I use


410
00:29:23,220 --> 00:29:24,510
the definition of the conditional


411
00:29:24,510 --> 00:29:27,720
probability it is the intersection of


412
00:29:27,720 --> 00:29:32,340
the set Y is smaller than X and the


413
00:29:32,340 --> 00:29:34,920
point was accepted divided by the


414
00:29:34,920 --> 00:29:37,550
probability that we accept the point


415
00:29:37,550 --> 00:29:40,740
okay so the probability that we accept


416
00:29:40,740 --> 00:29:50,490
the point it's just 1 divided by C this


417
00:29:50,490 --> 00:29:54,390
is 1 divided by C this was what we first


418
00:29:54,390 --> 00:29:59,360
observed ok so this is just a C times


419
00:29:59,360 --> 00:30:04,740
the probability that we are less than X


420
00:30:04,740 --> 00:30:09,090
raised to Y and the point is accepted


421
00:30:09,090 --> 00:30:12,960
now so the set of where the points are


422
00:30:12,960 --> 00:30:17,040
accepted so now I have again the


423
00:30:17,040 --> 00:30:22,830
situation here that I have a random


424
00:30:22,830 --> 00:30:26,160
variable Y yeah inside this probability


425
00:30:26,160 --> 00:30:29,130
and a random variable you inside this


426
00:30:29,130 --> 00:30:31,410
probability so actually I believe you


427
00:30:31,410 --> 00:30:33,960
was always Queen was you Queen yeah us


428
00:30:33,960 --> 00:30:36,270
on screen so maybe I marked this here


429
00:30:36,270 --> 00:30:42,330
for you so I have here you and why oh


430
00:30:42,330 --> 00:30:44,550
sorry not here so I would like to mark


431
00:30:44,550 --> 00:30:48,469
it here you and why


432
00:30:48,469 --> 00:30:49,890
and


433
00:30:49,890 --> 00:30:54,020
the same trick that we conditioned now


434
00:30:54,020 --> 00:31:00,420
know on some variable so let's condition


435
00:31:00,420 --> 00:31:05,260
on Y so let's fix y equals Z 

436
00:31:05,260 --> 00:31:05,270
on Y so let's fix y equals Z 

437
00:31:05,270 --> 00:31:10,610
on Y so let's fix y equals Z integrate over the whole density over


438
00:31:10,610 --> 00:31:10,620
integrate over the whole density over


439
00:31:10,620 --> 00:31:12,120
the whole domain and Marty is so


440
00:31:12,120 --> 00:31:16,230
multiplied with the density okay so all


441
00:31:16,230 --> 00:31:22,700
Y's are then replaced by the driven set


442
00:31:22,700 --> 00:31:25,970
actually I could have used a little Y


443
00:31:25,970 --> 00:31:35,160
okay and we integrate over the set


444
00:31:35,160 --> 00:31:37,170
multiplied with the density and recall


445
00:31:37,170 --> 00:31:42,060
we know the density of this guy which is


446
00:31:42,060 --> 00:31:50,490
y and now you see that what is this set


447
00:31:50,490 --> 00:31:54,270
here this is the probability that little


448
00:31:54,270 --> 00:31:58,440
Z is smaller than X and the uniform


449
00:31:58,440 --> 00:32:00,870
distributed random number u random


450
00:32:00,870 --> 00:32:03,300
variable U is smaller than this constant


451
00:32:03,300 --> 00:32:06,410
F of T divided by CG offset so now I


452
00:32:06,410 --> 00:32:09,300
integrate over set and here in the


453
00:32:09,300 --> 00:32:11,910
probability that is the condition Z is


454
00:32:11,910 --> 00:32:14,610
smaller than X so actually I can replace


455
00:32:14,610 --> 00:32:18,240
here the upper bound and I can get rid


456
00:32:18,240 --> 00:32:21,600
of this first part of the set so and


457
00:32:21,600 --> 00:32:26,550
since you know that this is a uniform so


458
00:32:26,550 --> 00:32:33,460
this guy here is a uniform


459
00:32:33,460 --> 00:32:37,300
you


460
00:32:37,300 --> 00:32:41,570
No so the probability of you smaller


461
00:32:41,570 --> 00:32:45,230
than little you is just little you so I


462
00:32:45,230 --> 00:32:49,670
can't just pluck this here here no and


463
00:32:49,670 --> 00:32:54,080
you have the density G from here and


464
00:32:54,080 --> 00:32:58,430
these two guys cancer now and you have


465
00:32:58,430 --> 00:33:02,180
one divided by C in front which cancers


466
00:33:02,180 --> 00:33:08,500
and this is now integrate F


467
00:33:08,500 --> 00:33:13,090
integrate f up to only X so this is the


468
00:33:13,090 --> 00:33:19,490
distribution function of


469
00:33:19,490 --> 00:33:22,890
this stupid version f of X so we have


470
00:33:22,890 --> 00:33:26,220
proven that X using this method has


471
00:33:26,220 --> 00:33:33,210
distribution function f okay so the


472
00:33:33,210 --> 00:33:35,610
method looks maybe a little bit


473
00:33:35,610 --> 00:33:37,710
complicated but actually it is not here


474
00:33:37,710 --> 00:33:39,510
you can have a very small implementation


475
00:33:39,510 --> 00:33:41,520
very clean you just need the densities


476
00:33:41,520 --> 00:33:44,400
two sequences check the condition accept


477
00:33:44,400 --> 00:33:50,070
or reject the point and you can as I


478
00:33:50,070 --> 00:33:53,610
already gave you some hints use this to


479
00:33:53,610 --> 00:33:56,580
perform a sampling of the normal


480
00:33:56,580 --> 00:33:59,250
distributed random variable yeah without


481
00:33:59,250 --> 00:34:01,710
actually using the distribution function


482
00:34:01,710 --> 00:34:04,290
of the normal distribution you just need


483
00:34:04,290 --> 00:34:08,370
some thing about the density and you can


484
00:34:08,370 --> 00:34:10,649
use the exponential distribution and the


485
00:34:10,649 --> 00:34:12,270
exponential distribution we can use with


486
00:34:12,270 --> 00:34:17,120
the inversion of T distribution function


487
00:34:17,120 --> 00:34:19,560
okay so maybe we have a court session


488
00:34:19,560 --> 00:34:21,629
with this or you can try it as an


489
00:34:21,629 --> 00:34:26,100
exercise that's it for today yeah thank


490
00:34:26,100 --> 00:34:29,330
you see you next time