Probabilistic Timing Estimates in Scenarios Under Testing Constraints

P obabilis ic Timing Es ima es in Scena ios
Unde Tes ing Cons ain s
Se gi Vila dell†, F ancesco Rossi∗, Gab iele Gio dana∗, Isabel Se a§,
En ico Mezze i†, Jaume Abella†, F ancisco J. Cazo la†
Ba celona Supe compu ing Cen e , Spain†
Uni e si a Au ònoma de Ba celona, Spain§
Aiko Space S. .l, I aly∗
Abs ac
Measu emen -based p obabilis ic (MBP) me hods like Ex eme Value
Theo y (EVT) and he Ma ko ’s Inequali y ha e been exploi ed o
de i e p obabilis ic Wo s -Case Execu ion Time (pWCET) es ima es.
Usually, he eliabili y and accu acy o pWCET echniques ha e
been e alua ed on medium o la ge sample sizes,
𝑁=[
10
3,
10
5]
.
Howe e , se e al wo ks inc easingly ad oca e o con aining he
cos o ca ying ou he es campaign by educing he numbe
o execu ions (i.e. he sample size) equi ed by pWCET analysis.
Speci ic scena ios, o example, impose inhe en limi a ions on he
collec ion o iming measu emen s due o cos and a ailabili y o
app op ia e es ing acili ies. In his wo k, we analyze he impac o
small sample sizes on MBP. Ou analysis shows ha classical EVT
models o ail es ima ion equi e a h eshold ha es ima es whe e
he ail o he dis ibu ion begins. In low sample scena ios, he
unce ain y in de e mining his h eshold can comp omise he eli-
abili y o EVT es ima es. We also assess he impac o small samples
on RESTK, a ime o ecas me hod based on Ma ko ’s Inequali y.
Ou esul s wi h syn he ic da a and ep esen a i e ke nels show
ha RESTK p o ides he bes ade-o in e ms o us wo hiness
and igh ness o small samples, pa ly due o no elying on he
selec ion o any h eshold, as opposed o EVT.
CCS Concep s
•Compu e sys ems o ganiza ion
→
Embedded sys ems;•
Ma hema ics o compu ing
→
P obabili y and s a is ics;•
Gene al and e e ence
→
Valida ion;Ve i ica ion;Reliabili y.
ACM Re e ence Fo ma :
Se gi Vila dell, F ancesco Rossi, Gab iele Gio dana, Isabel Se a, En ico
Mezze i, Jaume Abella, and F ancisco J. Cazo la. 2025. P obabilis ic Timing
Es ima es in Scena ios Unde Tes ing Cons ain s. In The 40 h ACM/SIGAPP
Symposium on Applied Compu ing (SAC ’25), Ma ch 31-Ap il 4, 2025, Ca ania,
I aly. ACM, New Yo k, NY, USA, A icle 4, 11 pages. h ps://doi.o g/10.1145/
3672608.3707895
© 2025 ACM. This is he AAM The de ini i e Ve sion o Reco d published in: Se gi
Vila dell, F ancesco Rossi, Gab iele Gio dana, Isabel Se a, En ico Mezze i, Jaume
Abella, and F ancisco J. Cazo la. 2025. P obabilis ic Timing Es ima es in Scena ios
Unde Tes ing Cons ain s. In P oceedings o he 40 h ACM/SIGAPP Symposium on
Applied Compu ing (SAC '25). Associa ion o Compu ing Machine y, New Yo k,
NY, USA, 560–569. h ps://doi.o g/10.1145/3672608.3707895.
Plan S Compliance: CC BY
1 In oduc ion
Digi iza ion in di e en domains is on he ise, wi h an inc easing
numbe o so wa e applica ions deployed o ealize a iche se o
unc ionali ies, om en e ainmen se ices o medical de ices and
manu ac u ing pipelines [
44
]. These so wa e applica ions in ol e
he use o complex AI-based algo i hms [
40
,
41
] ha demand high
le els o pe o mance ha can only be p o ided in an e icien man-
ne wi h complex he e ogeneous Common O The Shel (COTS)
compu ing pla o ms based on MPSoCs (Mul i P ocesso Sys em
on Chip).
A wide se o hese applica ions mus abide by i m o so eal-
ime equi emen s [
8
,
18
], i.e. no necessa ily ha d. So wa e iming
s ill ep esen s an impo an dimension in hese sys ems because,
while spo adic budge o e uns do no lead o ca as ophic conse-
quences, un imely execu ion may lead o hea ily deg aded ope a-
ion o unusable esul s. As an illus a i e example, le us conside
a GPS-based acking unc ion embedded in a sma wa ch: an occa-
sional deadline o e un in e eshing he GPS posi ion may a ec
he p ecision o he cu en posi ion bu will no cause he sys em
o ail. Clea ly, epe i i e deadline o e uns may e en ually lead o
a la gely inaccu a e posi ion and an unusable ack eco ding. Tim-
ing es ima es a e s ill equi ed o p o ide enough con idence in he
ac ha hose unc ionali ies will execu e mos o he imes wi hin
he alloca ed budge . Hence, a quali y p ocess is equi ed o assess
he accu acy o iming es ima es du ing p oduc de elopmen .
Measu emen -based p obabilis ic (MBP) me hods [5, 15, 34, 47]
a e inc easingly adop ed o de i e us wo hy iming uppe -bounds
in hose scena ios whe e, he combined complexi y o he ha d-
wa e pla o m (MPSoC) and so wa e applica ion p e en s he e -
ec i e applica ion o mo e consolida ed de e minis ic analysis ap-
p oaches [
7
,
27
,
40
,
41
,
48
,
52
]. MBP me hods ypically deli e es i-
ma es in he o m o an execu ion ime dis ibu ion ha , o any
gi en p obabili y
𝑝
, p o ides an execu ion ime bound (e b). The e b
can only be exceeded wi h a p obabili y
𝑞
such ha
𝑞≤𝑝
. Hence,
by choosing a su icien ly high e b, we can ob ain an a bi a ily
low, and hence, a o dable,
𝑝
(e.g., compa able o he accep able
ailu e a es o physical componen s in he sys em) e en o ha d
eal- ime sys ems, whe e he isk o o e un mus be educed d as-
ically (e.g., down o
[
10
−12,
10
−15]
). Some wo ks in he li e a u e
[6] p o ide a mo e comple e o mal de ini ion o his p oblem.
MBP me hods, mainly ocused on analyzing high-in eg i y sys-
ems, equi e he collec ion o housands o e en hund eds o hou-
sands o execu ion ime measu emen s samples o de i e us -
wo hy bounds o hose ex emely low exceedance p obabili ies
[
5
,
20
,
47
,
53
,
54
]. Howe e , collec ing such la ge samples may no
be always desi able o e en p ac ically easible. The collec ion o
la ge expe imen al da a can be impeded by he pa icula ly complex
unc ional and ope a ional scena io o he sys em unde analysis; o ,
mo e gene ally, es ing implies excep ional e o and cos s, so de e -
mining when o s op he es ing campaign becomes pa amoun o
a oid was e o ime and esou ces [
16
,
32
,
38
,
39
]. In his wo k, we
add ess wo undamen al ques ions: Can he lack o a la ge sample
p e en he applica ion o p obabilis ic me hods al oge he ? And, can
MBP echniques be used o p o ide bounds o p obabili y anges o
in e es o so and i m eal- ime applica ions (e.g.,
[
10
−4,
10
−6]
)?
The a ionale behind hose ques ions is ha , while ex eme a -
ge p obabili ies a e he mos easonable a ge o ha d eal- ime
c i ical sys ems, hey can be o e ly demanding o i m and so
eal- ime ones, whe e spo adic, in equen deadline misses can be
ole a ed. Fo hese sys ems, we migh no be in e es ed in he
ex eme ail o he execu ion ime dis ibu ion, bu less ex eme
iming beha io unde ela i ely highe p obabili ies, as his allows
in e cep ing occasionally (bu expec ed) high execu ion imes. In
hese cases, we con end i is easonable o ade some accu acy
o e iciency in he de e mina ion o p obabilis ic iming bounds
by applying p obabilis ic me hods on lowe sample sizes a he
cos o p oducing bounds ha a e modeling e en s wi h highe
p obabili ies.
In his pape , we p o ide a ca e ul analysis o he use o MBP
me hods o de i e execu ion ime bounds o i m and so eal-
ime applica ions in he p esence o small sample sizes. We build
on he conside a ion ha he main ocus o iming p edic ion in
hose sys ems is no on de e mining ex emely a e iming e en s
ha may no e en exis , bu a he on in e cep ing in equen bu
expec ed iming e en s. F om a p obabilis ic s andpoin , his means
we a e mainly in e es ed in de i ing igh iming es ima es o
e en s occu ing wi h p obabili ies in he ange
[
10
−4,
10
−6]
. In
pa icula , he con ibu ions o his pape a e as ollows:
(1)
We de elop on he speci ic p oblems b ough by he use
o small samples in he applica ion o EVT. We s udy he
heo e ical impac o small samples in EVT, show how o
compu e he unce ain y associa ed wi h he Maximum Like-
lihood Es ima ion (MLE) me hods ypically used in EVT, and
p opose o cap u e i using he Del a Me hod (Sec ion 3).
(2)
We show ha , a heo e ical le el, he RESTK me hod based
on he Ma ko ’s Inequali y, is no undamen ally a ec ed by
he use o small samples. Ins ead, he p oblems may a ise
wi h he applica ion me hodology. In ha line, we show how
de i a ion o he maximum alue o
𝑘
and he de i a ion
o momen s equi es o be changed o small samples (Sec-
ion 4).
(3)
We e alua e bo h MBP amily o me hods on a se o ex en-
si e syn he ic dis ibu ions, a ep esen a i e ke nel (ma ix
mul iplica ion), and wo case s udies ( ailway and space). Re-
sul s on syn he ic and eal da a con i m ha me hods based
on Ma ko ’s Inequali y s and ou o hei us wo hiness
and igh ness e en in low sample scena ios (Sec ion 5).
The es o his pape is o ganized as ollows: Sec ion 2 de elops
he p oblem add essed in his wo k and in oduces he mos ele an
backg ound. Sec ion 3 de elops on he main p oblems ha he use o
small samples b ings o he applica ion o EVT. Likewise, Sec ion 4
p esen s how small samples a ec he applica ion o he Ma ko ’s
... 10-2 10-3 10-5
10-4 10-6 10-7 10-8 10-10
10-9 10-12
10-11 10-13 10-14 10-15 ...
Video Playing
Mission C i ical
Low-F equency
Sa e y C i ical
High-F equency
Sa e y C i ical
Timing Failu e P obabili y
Figu e 1: Timing ailu e p obabili y con inuum. Re e ence
anges ha in eali y depend on he pa icula domain and
applica ion.
Inequali y. Sec ion 5 quan i a i ely compa es bo h me hods. The
pape concludes wi h Sec ion 6 ha summa izes he main ela ed
wo ks and Sec ion 7 ha p esen s he main ake away messages
om his s udy.
2 Mo i a ion
When i comes o isk assessmen ac oss di e en applica ion do-
mains, he majo i y o sa e y egula ions a e based on he As Low As
Reasonably P ac icable (ALARP) enginee ing p inciple, which es ab-
lishes ha isk ole ance shall be assessed agains he p ac icali y
o he applied isk- educ ion echniques. In he con ex o es ing,
he bene i o mo e p ecise es ima ions has o be p opo ioned o
he ime and e o equi ed o apply he WCET echniques [
38
].
Fo measu emen -based echniques his las aspec is ul ima ely
ela ed o he numbe o es s/ uns, a.k.a. sample size.
•
Cos s. Limi a ions may a ise because applica ions in e ac in
a complex en i onmen wi h he ex e nal wo ld, which may
equi e speci ic acili ies, ools, o de ices [
16
,
39
], such in, o
example, on- he- oad es ing in au omo i e. The cos and/o a ail-
abili y o adequa e measu emen se ups o simply he compelling
need o educe he cos and ime de o ed o iming analysis, in
p ojec s ha a e o en conduc ed unde se e e ime p essu e,
push owa ds sho es campaigns [
32
]. This can be u he
compounded by di icul ies o ully au oma e he p ocess ha
makes he collec ion o measu emen s a cumbe some p ocess. All
hese complica ions ha e mo i a ed some me hods o asce ain
whe he enough es s ha e been pe o med in a iming analysis
campaign [38].
•
Bene i s. So wa e iming is a non- unc ional aspec o execu ion
ha is no uni o mly pe cei ed ac oss indus ial domains. Fo
many mains eam applica ions, iming is mainly ecognized as a
quali y aspec wi h as e o slowe execu ion being app ecia ed
as good o deg aded o e all pe o mance o a p oduc . Fo o he
applica ions, he concep s o iming misbeha io and iola ions
a e a ached o mo e o less i m equi emen s on he maximum
execu ion ime aken o deli e a esul . The impac o a iming
budge o e un may a y depending on he applica ion domain
and he execu ion con ex , anging om p oduc de e io a ion
and economic loss o en i onmen al disas e s and casual ies.
This elas ici y o iming equi emen s o ime- ela ed applica-
ions leads o a p obabili y con inuum ep esen ing he ole ance
agains sys em iming ailu es [31], illus a ed in Figu e 1.
•
En e ainmen sys ems (e.g. ideo and/o audio playing): iming
ailu e a es in he o de o
[
10
−2,
10
−4]
can be expe ienced
wi hou a ec ing he use expe ience. Fo ins ance, assuming 25
FPS ideo playing, a aul y ame e e y 4 o 400 seconds is o en
ole able.
•
Payloads in mission-c i ical sys ems like unmanned explo a o y
space missions, wi h ins umen s collec ing and p ocessing da a
in eal- ime: he sys ems ope a ing hose ins umen s can a o d
some spo adic ailu es ha may deg ade he success o he mis-
sion, bu do no deg ade i no iceably i hey a e spo adic enough.
Hence, ailu e a es in he o de o
[
10
−4,
10
−6]
a e usually a o d-
able (i.e. once e e y ew minu es o ew hou s o ins umen s
collec ing and p ocessing one image a 25 FPS).
•
Elec onic ea - iew mi o s in mode n ca s, eplacing eal mi -
o s wi h came as and ideo displays: in his case, ideo playing
is no jus o en e ainmen pu poses bu o assis ing humans
in c i ical ope a ions such as d i ing. They equi e e en lowe
iming ailu e a es as hey inhe i some (low) in eg i y equi e-
men s.
•
Las ly, o he sys ems a e sa e y-c i ical (high in eg i y equi e-
men s), e.g. con olling he ope a ion o an au onomous d i ing
ca : he consequences o a misbeha io o he sys em iming ail-
u e a es a e usually ela ed o hose de ined by sa e y s anda ds
o ha dwa e ailu e a es ha , while applica ion-domain speci ic,
usually ange in
[
10
−9,
10
−12]
pe hou . Depending on he e-
quency o execu ion o he ask unde analysis, his migh esul
in lowe a ge p obabili ies o iming ailu e pe applica ion. Fo
ins ance, i he applica ion execu es 1,000 imes an hou (10
3
) he
a ge ailu e a e ange would be [10−12,10−15]o lowe [15].
O e all, di e en applica ion domains, and applica ions wi hin
he same domain, exhibi di e en iming equi emen s. End use s
mus p o ide quali y assu ance so ha hei p oduc s beha e as
expec ed. The ise o complex MPSoCs has consolida ed he use
o MBP me hods ha mus p o ide adequa e es ima es wi h he
ALARP numbe o measu emen s (samples). The la e answe s he
need o educe he applica ion cos o MBP me hods and, in some
cases, o cope wi h he una ailabili y o la ge samples [
16
,
32
,
38
,
39].
3 EVT o Small Samples
In all applica ion domains, he use o high-quali y inpu da a (e.g.,
high- es images) and AI so wa e equi es he adop ion o high-
pe o mance MPSoCs o p o ide he necessa y le els o pe o -
mance. As sys em complexi y has inc eased, and MPSoCs become
mo e popula , MBP me hods gained a ac ion due o hei abili y
o cap u e and analyze he excep ional le el o a iabili y eme g-
ing in execu ion ime measu emen s o AI so wa e unning on
MPSoCs [7, 40, 41].
The a ge o he p oposed MBP solu ions has been de i ing e b
p edic ing he p obabili y o exceeding pa icula ly high execu ion
imes, o en ocusing on hose alues exceeded wi h p obabili ies in
he ange
[
10
−9,
10
−15]
. In o de o ob ain us wo hy p edic ions
o such low exceedance p obabili y anges, he numbe o exe-
cu ion ime measu emen s ha need o be collec ed can be in he
o de o housands o e en hund eds o housands [5, 20, 47, 54].
We a e in e es ed in explo ing he applica ion o MBP solu ions
in a di e en con ex conside ing highe exceedance p obabili y
anges and educed sample sizes. While he e is no heo e ical
obs acle o he applica ion o MBP o he new se ups, al e ing he
applica ion condi ions o he me hods (i.e. educing da a a ailable
o he p edic ions and a ge ing highe exceedance p obabili ies)
has clea implica ions on he inal ou come o each MBP me hod,
and needs app op ia e analysis and e alua ion. Unde s anding and
assessing MBP me hods unde hese new condi ions is he main
goal o his pape .
Classical ex eme alue s a is ics [
51
] consis s o wo undamen-
al app oaches: selec ing he maximum alues o slices o you
da a, he Block Maxima app oach (BM), o selec ing a h eshold
om which he o de s a is ics abo e i a e conside ed ex emes,
he Peaks o e Th eshold (PoT) app oach. In his wo k we ocus on
he second one, o wo easons.
•
Fi s , we a e in e es ed in modeling he ail o he dis ibu ion
ins ead o he maxima.
•
And second, i has been shown ha o small sample sizes,
𝑁<
100, when bo h me hods use he whole sample, he PoT app oach
makes mo e e icien use o he da a in gene al [11].
The PoT app oach equi es add essing he challenge o de ining
he selec ion o he h eshold ha de e mines when he ail o he
dis ibu ion s a s. The limi ing dis ibu ion on he ail o a andom
a iable, as desc ibed by he undamen al heo em o EVT, is he
Gene alized Pa e o Dis ibu ion (GPD) [
1
]. Le us de ine he GPD
law as:
𝐺(𝑦;𝜎, 𝜉)=





1−1+𝜉𝑦
𝜎−1
𝜉i 𝜉≠0,
1−exp−𝑦
𝜎i 𝜉=0,
(1)
whe e
𝜎
is he scale pa ame e and
𝜉
is he shape pa ame e , also
known as he ex eme alue index. This law conside s h ee ypes
o ails depending on he alue o he ex eme alue index. Fo
𝜉>
0we ha e hea y ails, o
𝜉=
0we ha e exponen ial ails,
and o
𝜉<
0we ha e ligh ails. The GPD law has he ollowing
cons ain s o ligh ails, when
𝜉<
0, on he pa ame e s
𝜎>
0,
and
𝑦≥
0when
𝜉≥
0and 0
≤𝑦≤𝜎/𝜉
. In his wo k we ocus on
he GPD wi h
𝜉≤
0, which o
𝜉=
0is an exponen ial ail, and o
𝜉<
0is he GPD wi h ligh ails (GLT). We es ic o
𝜉≤
0gi en
ha he exponen ial ail is ega ded as an uppe bound o ex eme
quan ile p edic ion [28].
In his sec ion, we de elop on he impac ha small samples
ha e on h ee di e en au oma ed ail h eshold selec ion me hods
and speci ically on hei pe o mance on ex eme alue es ima ion.
The selec ed me hods ake a di e en app oach o ail h eshold
es ima ion, which ensu es a wide and mo e ep esen a i e scope
o ou analysis.
(1)
Fi s , we conside a semi-pa ame ic (SP) model [
10
] based
on simul aneously i ing a semi-pa ame ic unc ion on he
bulk o he dis ibu ion, and a GLT o exponen ial (no mally
conside ed in EVT me hods o iming es ima ion) on he
ail, successi ely adjus ing he h eshold ha maximizes he
likelihood wi h he mix u e o he wo models.
(2)
Second, we ocus on he QQ me hod [
4
], le e aging a me -
ic ha minimizes he dis ance be ween he i ed GLT o
exponen ial and he es ima ed quan iles o he boo s ap
sample.
(3)
Finally, we also use he CV plo [
30
] me hod, based on he
so-called coe icien o a ia ion and used in p e ious WCET-
ela ed wo ks [28].
O e all, hese h ee di e en app oaches a e expec ed o exhibi
di e en h esholds and unce ain ies on he es ima ion.
Theo e ical unce ain y analysis. P oducing high-quan ile
es ima ions in low sample scena ios can incu a Bias-Va iance p ob-
lem [
17
] gi en ha he e may be jus ew poin s le a e selec ing
a p ope h eshold. In his wo k we aim o assess he impac o
low samples in EVT models om a heo e ical poin o iew. In
he me hodologies we show, we can isola e one pa o he model
unce ain y. The CV, QQ and SP me hods, all need o pe o m i s
an es ima ion o he ex eme alue index
𝜉
, which ep esen s he
i s sou ce o unce ain y in he models. The e o e, he unce ain y
on he es ima ion o
𝜉
is a lowe bound o he unce ain y o he
model. Fo low sample scena ios, i he unce ain y on he es ima-
ion o
𝜉
by i sel is al eady high, hen he unce ain y will u he
p opaga e wi hin he models.
3.1 CV Plo
The basis o his me hod is in he Coe icien o Va ia ion (CV),
which is he a io be ween he s anda d de ia ion and he expec ed
alue o he dis ibu ion. Taking he sample a iance
ˆ
𝑉(𝑋)
and he
sample mean ˆ
𝐸(𝑋)we ha e he sample CV:
bc =√︃ˆ
𝑉(𝑋)
ˆ
𝐸(𝑋).(2)
As we a e in e es ed in he ail, we can de ine he esidual CV as
he CV o he alues abo e a h eshold
𝑢
. Le he excess mean be
𝐸(𝑋−𝑢|𝑥>𝑢)
and he excess a ia ion be
𝑉(𝑋−𝑢|𝑥>𝑢)
hen
he sample esidual CV is:
bc 𝑢=√︃ˆ
𝑉(𝑋−𝑢|𝑥>𝑢)
ˆ
𝐸(𝑋−𝑢|𝑥>𝑢),(3)
The esidual CV is almos cons an o a su icien ly high h esh-
old [30], and his is he case o he GLT.
In e es ingly, as we de elop below, i
bc gpd
and
b
𝜉
a e maxi-
mum likelihood es ima o s (MLE), and wi h
𝑉gpd (𝑋−𝑢|𝑥>𝑢)=
𝜎2
(1−ˆ
𝜉)2(1−2ˆ
𝜉)
and
𝐸gpd (𝑋−𝑢|𝑥>𝑢)=𝜎
(1−ˆ
𝜉)
he esidual CV o
he GLT can be exp essed as:
bc gpd =𝜎
(1−ˆ
𝜉)√︃(1−2ˆ
𝜉)/𝜎
(1−ˆ
𝜉)
=1
√︃(1−2ˆ
𝜉)
.(4)
Fo high enough h esholds, he esidual CV is cons an , hus
he esidual CV is an es ima o o he ex eme alue index
𝜉
. Fo
exponen ial ails, i.e.
𝜉=
0, he esidual CV is 1, which makes i
a pa icula ly use ul ool o inding exponen ial h esholds. Fo
𝜉≠
0, one should ind he h eshold om which he esidual CV is
cons an and hen compu e 𝜉.
Applica ion o small samples. Fo small samples, he s abiliza-
ion o he esidual CV can be challenging. I we conside samples
o he o de
𝑁=
100, and conside a h eshold a he 75% quan ile,
i lea es us 25 da a poin s, which is enough o es ima e he mean
and a iance o he sample and hence can lead o p ope es ima es
o he esidual CV [23].
We explo e he asymp o ic a iance o show a bound on un-
ce ain y ela ed wi h he sample size. Conc e ely, we p opose o
cap u e i s unce ain y using he Del a Me hod [
26
], which can
be applied o de ining he unce ain y o a s a is ic ha is asymp-
o ically Gaussian. The Del a me hod is a gene aliza ion o he
concep o p opaga ion o e o , which is widely used in science
o accu a e ep esen a ions o complex unce ain ies. In his case,
we compu e he con idence in e als a ound he esidual CV in
Equa ion 4, whe e he
𝜉
is compu ed wi h MLE, he e o e making
he esidual CV an asymp o ically no mal es ima o . Following his
a gumen , we use he gene al e sion o he Del a Me hod:
√𝑁[𝑔(ˆ
𝜃) −𝑔(𝜃)] 𝑑
−→ N(0, 𝜎2[𝑔′(𝜃)]2),(5)
conside ing ha he de i a i e o
𝑔
a
𝜃
exis s and is no ze o.
Acco dingly, we exp ess he unce ain y o he esidual CV as:
√𝑁[bc gpd −c gpd]𝑑
−→ N(0, 𝜉2[c ′
gpd (𝜉)]2).(6)
Finally, we compu e he de i a i e and ob ain an exp ession o
he unce ain y a ound he es ima o as a unc ion o he sample
size:
bc gpd ≈ N(c gpd, 𝜉2|(1−2𝜉)−3|/𝑁).(7)
Example
. In o de o isola e he unce ain y a ound he esidual
CV as an es ima o o
𝜉
, le ’s conside a PoT model wi h a GLT
wi h h eshold a quan ile
𝑝=
0
.
9and scale pa ame e
𝜎=
1, and
compu e he heo e ical ex eme quan ile
𝑝=
1
−
10
−6
. We choose
an ex eme alue index
𝜉1=−
0
.
5and wi h Equa ion 7 we can
compu e he 95% con idence in e al o a sample size o
𝑁𝑢=
10
alues, which would be he excess sample size wi h a h eshold a
𝑝=
0
.
9wi h a base sample o
𝑁=
100. Compu ing all numbe s, he
con idence in e al o he esidual CV on
𝜉1=−
0
.
5(wi h a alue
o
c 1=
0
.
71) is
bc 1=[
0
.
72
,
0
.
69
]
, which is a di e ence o 4
.
7%. On
a simila example, wi h
𝜉2=−
0
.
25 (wi h
c 2=
0
.
81) has a esidual
CV o
bc 2=[
0
.
82
,
0
.
80
]
, which also hi s a 2% di e ence. Recall ha
we ix all pa ame e s and his is he e ec on low sample size only
on he es ima ion o he esidual CV, which is used o es ima e he
h eshold. I we accoun o he unce ain y om he es ima ion o
he ex eme alue index, hen he unce ain y a ound he esidual
CV d ama ically inc eases.
3.2 QQ plo me ic
This me hod p oposes a me ic based on he QQ plo , which is
o be minimized. In pa icula , he me ic is he mean absolu e
di e ence be ween he i ed model and he sample quan iles on
he ail. Based on he me hodology shown in [
12
], we conside bo h
he boo s apped (QQB) and non-boo s apped (QQ) e sions, he
la e been used in [4].
Le
𝑋𝑢=(𝑋−𝑢|𝑥>𝑢)
be he excess sample abo e a h eshold
𝑢
, hen le
𝑋𝑏
𝑢
be he b h boo s ap sample. In a wo k o he s a e
o he a [
12
], he selec ed boo s apped sample size is se o be
he same size as he excess sample
𝑋𝑢
gi en a h eshold
𝑢
. Le
𝑄(𝑝, 𝑋𝑢)
be he sample quan ile unc ion, which in he same wo k
[
12
] is based on linea in e pola ions [
24
]. The p obabili ies o
he quan iles checked a e based on wo pa ame e s which can be
chosen
𝑝𝑗 = 𝑗/(𝑚 +
1
)
:
𝑗 =
1
, · · · , 𝑚
. Then, he QQ plo based
me ic eads as
𝑑𝑏(𝑢)=1
𝑚
𝑚
∑︁
𝑗=1
ˆ
𝜎𝑏
𝑢
ˆ
𝜉𝑏
𝑢h(1−𝑝𝑗)ˆ
𝜉𝑏
𝑢−1i−𝑄(𝑝𝑗, 𝑋𝑏
𝑢),(8)
whe e
ˆ
𝜎𝑏
𝑢
and
ˆ
𝜉𝑏
𝑢
a e he boo s apped scale and shape o he h esh-
old
𝑢
espec i ely. The non-boo s apped e sion is essen ially he
same me hodology bu using only he excess sample
𝑋𝑢
once o
each h eshold. Fo la ge samples, his me hod p o ides a good
me ic o h eshold selec ion. I is able o p o ide a good comp o-
mise be ween Bias and Va iance. No e ha , o high h esholds,
he i ing migh no be igh because o spa se da a in he ails.
Con e sely, o low h esholds, he i ing migh no be igh gi en
we a e no in he ail.
Applica ion o small samples. The e o e, he QQ plo based
me ic is able o comp omise and ind p ope h esholds o ei-
he he GLT o exponen ial ails. Howe e , in a small sample size
scena io, he minimum o he me ic, which is used o selec he
h eshold alue, migh be mo e elusi e. Gi en he small amoun o
da a and high a iance be ween alues, he minimum dis ance may
be oo close o he ail, p o iding less ce ain y o a p ope h eshold
selec ion. In he nex sec ion, we o malize he unce ain y a ound
he quan ile es ima ion p oduced by he MLE o he ex eme alue
index.
3.3 Semipa ame ic model
The PoT me hodology is based on modeling he ail o a dis ibu ion
wi h a pa ame ic model, i.e. a GLT, abo e a ce ain h eshold
𝑢
.
The i ing o a pa ame ic model pe mi s he compu a ion o he
likelihood o he sample belonging o he selec ed model. In he
case o PoT, he ail model is known because heo e ically he GLT
is he app op ia e model. O he wise, he model o he bulk can
be pa ame ic (e.g. i ing a Weibull dis ibu ion), non-pa ame ic
(compu ing he empi ical dis ibu ion unc ion), o semi-pa ame ic,
which is he one we use in his wo k. A semipa ame ic model is
a model whe e he e can be a speci ica ion o an analy ical model
wi h ixed pa ame e s, bu ano he componen o he model may
no be known and be in ini e-dimensional. Fo ins ance, he Weibull
Mix u e model is a semipa ame ic model because while an analy ic
dis ibu ion wi h ini e pa ame e s, he numbe o componen s (i.e.
he di e en Weibulls composing he mix u e) is nei he bounded
no known. The mo i a ion behind combining a ail model wi h a
bulk model, is o selec a h eshold ha maximizes he likelihood
o he models on he bulk and he ail a once. The likelihood o a
PoT semipa ame ic model akes he o m:
𝐿PoT
gl (𝑋)=𝐿bulk (𝑋)(1−𝐻(𝑢|𝛾))𝐿gl (𝑋)(9)
=Ö
𝑥𝑖≤𝑢
ℎ(𝑥𝑖|𝛾)Ö
𝑥𝑖>𝑢
1−𝐻(𝑢|𝛾)
𝜎1+𝜉𝑥𝑖−𝑢
𝜎−(1+𝜉)
𝜉,
(10)
in he case o he GLT, whe e
ℎ(𝑥𝑖|𝛾)
is he model o he bulk wi h
a pa ame e 𝛾 o une. Fo he exponen ial case:
𝐿PoT
exp (𝑋)=𝐿bulk (𝑋)(1−𝐻(𝑢|𝛾))𝐿exp (𝑋)(11)
=Ö
𝑥𝑖≤𝑢
ℎ(𝑥𝑖|𝛾)Ö
𝑥𝑖>𝑢
1−𝐻(𝑢|𝛾)
𝜎exp−𝑥𝑖−𝑢
𝜎.(12)
In ha way, compa ing models wi h di e en h eshold o he
GLT and exponen ial is possible because he sample size is ixed.
Cab as e al. [
10
] p opose a semipa ame ic me hod conside ing
he GLT o exponen ial dis ibu ion o he ail, and using he
Lindsay me hod [
25
] o une he model
ℎ(𝑥𝑖|𝛾)
o he bulk o he
dis ibu ion. A semipa ame ic model can be i ed o he bulk by
adjus ing a ke nel unc ion in o mul iple windows in he p obabili y
dis ibu ion unc ion. The numbe and size o he windows is wha
makes he model semipa ame ic, because hey a e unknown a
p io i. Lindsay p oposes a me hod o i he op imal window size
and numbe o adjus he bulk smoo hly.
Applica ion o small samples. The me hodology p esen ed in
[
10
] p oduces sa is ac o y esul s, howe e in a small sample sce-
na io i may be di icul o ind a obus es ima ion o bo h models
o he bulk and he ail. This may lead o high unce ain y in he
h eshold selec ion. Mo e o mally, as pa o he analysis in his
wo k, we compu e he unce ain y associa ed wi h he Maximum
Likelihood Es ima ion (MLE) me hods ypically used in EVT. The
p ocess o i ing ails o a dis ibu ion and es ima ing quan iles ou -
side o he obse ed sample p oduces se e al sou ces o unce ain y.
Unce ain y equally s ems om he h eshold selec ion, he de e -
mina ion o scale pa ame e and ex eme alue index o he GLT,
and he quan ile unc ion used o ob ain quan ile es ima ions. In
his wo k, we isola e all sou ces o unce ain y om he es ima ion
o he ex eme alue index, hus p oducing a lowe bound o he
unce ain y associa ed o using small samples on EVT echniques.
We show how e en a single sou ce o unce ain y can be signi ican
when dealing wi h small samples. Fo he SP and he QQ me hod,
we use he MLE o
𝜉
o GLT. This es ima o p oduces he lowes
a iance gi en ha i assumes he C ame -Rao bound [
42
,
45
]. In
ac , MLE asymp o ically con e ges in law o a no mal dis ibu ion
N(0, 𝜎2)wi h mean 0and a iance 𝜎2as,
√𝑁[ˆ
𝜃−𝜃]𝑑
−→ N(0, 𝜎2),(13)
whe e
𝑁
is he sample size,
ˆ
𝜃
is he MLE o he ue pa ame e ,
𝜃
. Whe e he C ame -Rao bound o
𝜃
is: The C ame -Rao bound
eads as:
a (𝜃) ≥ 1
𝐼(𝜃)(14)
whe e 𝐼is he Fishe in o ma ion de ined as:
𝐼(𝜃)=−𝐸𝜕2
𝜕𝜃2log(𝑓(𝑋;𝜃))|𝜃(15)
In o de o de i e he C ame -Rao bound o he pa icula case o
GLT, we apply he MLE o he ex eme alue index 𝜉
𝜕𝐿gl
𝜕𝜉 =−1
𝜉+1
𝜉2
𝑁
∑︁
𝑖=1log1+𝑦𝑖
𝜙=0(16)

whe e
𝑦
and
𝜙
a e he sample and scale pa ame e espec i ely o
he ail. Then, we ob ain he es ima o ,
ˆ
𝜉=
𝑁
∑︁
𝑖=1
log(1+𝑦𝑖/𝜙).(17)
Now, we can compu e he Fishe in o ma ion:
𝜕2𝐿gl
𝜕𝜉2=1
𝜉2−2
𝜉3
𝑁
∑︁
𝑖=1
log1+𝑦
𝜙=1
ˆ
𝜉2−2
ˆ
𝜉3
ˆ
𝜉=−1
ˆ
𝜉2(18)
Finally, he C ame -Rao bound is as ollows:
a (𝜃) ≥ 1
𝐼(𝜃)=1
−(− 1
ˆ
𝜉2)
=ˆ
𝜉2(19)
This esul shows us he lowes a iance on he es ima o o
𝜉
,
which we plug in o Equa ion 13 o ob ain i s con idence in e al:
√𝑁[ˆ
𝜉−𝜉]𝑑
−→ N(0, 𝜉2).(20)
This exp ession o he GLT cap u es how a low sample size can
a ec he unce ain y a ound he es ima ion.
Example
. Le ’s assume a sample size o
𝑁=
100, simula ing a
h eshold a quan ile
𝑝=
0
.
9, we ha e an excess sample size o
𝑁𝑢=
10 o pe o m MLE on
𝜉
. We compu e he 95% con idence in e -
al o
𝑁𝑢=
10, o
𝜉1=−
0
.
5, which gi es
ˆ
𝜉1∈ [−
0
.
34
,−
0
.
65
]
; and
𝜉2=−
0
.
25, which gi es
ˆ
𝜉2∈ [−
0
.
21
,−
0
.
29
]
. I we compa e hese
con idence in e als o a bigge sample scena io, wi h
𝑁=
1000,
simula ing a h eshold a quan ile
𝑝=
0
.
9, esul ing in an excess
sample size o
𝑁𝑢=
100, we obse e i yields
ˆ
𝜉1∈ [−
0
.
45
,−
0
.
55
]
and
ˆ
𝜉2∈ [−
0
.
23
,−
0
.
26
]
which a e much na owe con idence in-
e als.
To isola e he e ec o he unce ain y a ound
𝜉
on he ex eme
quan ile es ima ion le us conside a PoT model wi h a GLT wi h
h eshold a quan ile
𝑝=
0
.
9and scale pa ame e
𝜎=
1, and
compu e he heo e ical ex eme quan ile
𝑝=
1
−
10
−6
. We use he
con idence in e als on
ˆ
𝜉1
and
ˆ
𝜉2
and p opaga e he e o o he
quan ile es ima ion
𝑁𝑢=
10. The con idence in e als o quan ile
𝑝=
1
−
10
−6
on
ˆ
𝜉1
is
ˆ
𝑞1∈ [
5
.
47
,
4
.
39
]
, o a 24% di e ence; while
o
ˆ
𝜉2
i is
ˆ
𝑞2∈ [
3
.
87
,
2
.
52
]
, esul ing in a 53% di e ence. Wi h
he examples abo e, we show he minimum a iance we would
see in hese me hodologies o low sample scena ios, gi en ha
in he examples we a e no accoun ing o he addi ional a iance
incu ed by he p opaga ion o unce ain y o each me hodology.
O e all, om he analyses we ha e p esen ed we conclude ha
he small sample size has a la ge impac on he unce ain y o he
models by de ini ion. The e o e, he e is need o assess he impac
o low samples in an empi ical way.
4 Ma ko ’s Inequali y wi h Small Sample Sizes
4.1 In oduc ion o Ma ko ’s Inequali y and
RESTK
Ma ko ’s Inequali y (MI) [
3
] pe ains o he p obabilis ic concep o
concen a ion inequali ies, whe e he p obabili y o an independen
andom a iable being highe o lowe han a ce ain alue
𝑏
can be
lowe - o uppe -bounded. In he case o MI, he exp ession uppe -
bounds he cumula i e p obabili y as
𝑃(𝑋≥𝑏) ≤ 𝐸(𝑋)
𝑏,(21)
whe e
𝐸(𝑋)
is he expec ed alue and
𝑏
is a alue pe aining o he
dis ibu ion o he andom a iable 𝑋>0. This pa icula o m o
MI is no usable in p ac ice o ex eme alues due o i s pessimism.
Vila dell e al. [
54
] use he pa icula case o MI wi h he powe -o -k
unc ion (MIK),
𝑃(𝑋≥𝑏) ≤ 𝐸(𝑋𝑘)
𝑏𝑘,(22)
whe e
𝐸(𝑋𝑘)
a e he heo e ical momen s o he dis ibu ion. Gi en
ha , in gene al, he heo e ical momen s o a dis ibu ion a e un-
known, he au ho s adap ed he heo e ical e sion o he inequali y
using he heo e ical momen s, o he e sion whe e he momen s
a e es ima ed om he sample,
𝑃(𝑋≥𝑏) ≤ 1
𝑁Í𝑁
𝑖𝑥𝑘
𝑖
𝑏𝑘,(23)
whe e
Í𝑁
𝑖𝑥𝑘
𝑖/𝑁
is he sample momen es ima o [
43
]. This adap a-
ion o MIK wi h he sample momen es ima o pe mi s he uppe -
bounding o any posi i e andom a iable
𝑋>
0. Un o una ely,
igh ly uppe -bounding ex eme alues equi es inc easing he
alue o
𝑘
, and he sample momen es ima o , while being a good
es ima o o highe o de momen s, is inconsis en o inc easing
alues o
𝑘
. Vila dell e al. [
54
] de ise he Res ic ed k(RESTK) algo-
i hm, whe e a maximum alue o
𝑘
, named
max𝑘
is ixed o each
a ge p obabili y o ensu e uppe -bounding. In RESTK, he cen al
pa o he algo i hm consis s o inding he
max𝑘
cu e, which in-
dica es he maximum
𝑘
o be used in he sample momen es ima o
in o de no o unde es ima e. The p oblem is ha o quan iles
ou side he sample ange, i is no possible o assess he unde es-
ima ion. The key inding is ha he ela ionship be ween
max𝑘
and he loga i hm o he p obabili y is linea . The e o e, RESTK can
ind
max𝑘
o he p obabili ies wi hin he sample size, and hen
p ojec
max𝑘
owa d lowe p obabili ies ou side he sample wi h a
linea p ojec ion.
In Algo i hm 1, we show he pseudo-code necessa y o compu e
he
max𝑘
cu e. I builds on a gi en sample o size
𝑁
and he a ge
p obabili ies o uppe -bound
𝑝 a ge
ha will be ou side o he ange
o he sample. Then, RESTK selec s he p obabili ies o he quan-
iles wi hin he sample,
𝑝samp
, which should be smalle han 1
/𝑁
o accu a e es ima es. Fo each p obabili y wi hin he sample size
selec ed, in Line 3, RESTK uses he quan ile es ima o sugges ed in
[
24
] gi en ha i is app oxima ely unbiased in he median. Then,
o each quan ile es ima ed,
𝑞es
, RESTK inds he smalles alue
o
𝑘
ha does no unde es ima e. In o de o achie e ha , RESTK
pe o ms
𝑛boo sims
numbe o boo s ap simula ions, wi h each boo -
s ap sample,
samp𝑏
, o size
𝑛𝑏
. Line 6 shows how RESTK inds he
minimum be ween he quan ile es ima ion made by MIK wi h he
sample momen es ima o shown in Equa ion 23, and he es ima ed
quan ile om he sample,
|MIK(𝑘, sampb, 𝑝) − 𝑞samp|
. The mini-
mum is ob ained op imizing
𝑘
o he boo s ap sample
𝑛𝑏
. Finally,
he algo i hm keeps he smalles
𝑘
om all boo s ap simula ions,
which will be he
max𝑘
o ha p obabili y. Once he
max𝑘
a e
Algo i hm 1 RESTK algo i hm o ob ain he max𝑘cu e.
1: unc ion RESTK(sample,𝑛b,𝑛boo sims,𝑝samp,𝑝 a ge )
2: o 𝑝∈𝑝samp do
3: 𝑞samp ←sampleQuan ileEs ima ion(sample, 𝑝)
4: o sim ∈𝑛boo sims do
5: sampb←boo s ap(sample,𝑛b)
6: cu en 𝑘(𝑝) ← indMinOnK|MIK(𝑘, sampb, 𝑝) −𝑞samp |
7: i cu en 𝑘(𝑝)<max𝑘(𝑝) hen
8: max𝑘(𝑝)=cu en 𝑘(𝑝)
9: end i
10: end o
11: end o
12: max𝑘(𝑝 a ge ) ← linea Adjus (max𝑘(𝑝samp ), 𝑝 a ge )
13: e u n max𝑘(𝑝 a ge )
14: end unc ion
compu ed o all
𝑝samp
, RESTK cons uc s he
max𝑘
cu e in Line
12 by compu ing he linea p ojec ion o he a ge p obabili ies
𝑝 a ge
in he linea o m
max𝑘(𝑝)=𝛼log(𝑝)+𝛽
, gi en ha he
max𝑘
and
𝑝 a ge
ha e been es ima ed. Then RESTK es ima es he
max𝑘(𝑝 a ge )
using he es ima ed pa ame e s o he linea adjus ,
ˆ
𝛼, ˆ
𝛽
and
𝑝 a ge
. Finally, RESTK can uppe -bound he quan iles wi h
p obabili y
𝑝 a ge
by compu ing MIK wi h a maximum alue o
max𝑘(𝑝 a ge ).
RESTK has been es ed o low p obabili ies be ween
𝑝=[
10
−12,
10
−15]
, which equi ed sample sizes o
𝑁=
10
6
[
54
]. Al hough he
esul s we e sa is ac o y o ex emely high quan iles using big
sample sizes, i emains o be unde s ood how o use RESTK in
small sample scena ios.
4.2 Impac o Small Samples on RESTK
In con as o EVT, MI uses he whole sample and, he e o e, he e
is no need o il e ing ou he da a using a h eshold alue. Howe e ,
he pa ame iza ion o MIK wi h RESTK used on la ge sample sizes
canno be used in he same way on small ones.
max
𝑘
es ima ion. In RESTK, he key pa o he algo i hm is
inding he
max𝑘
cu e, de e mining he maximum
𝑘
o be used in
he sample momen es ima o in o de no o unde es ima e.The
p obabili ies o he quan iles es ima ed wi hin he sample we e
𝑝samp ={
10
−3,
10
−4,
10
−5}
. Those quan iles we e used o he lin-
ea p ojec ion o a ge p obabili ies ou side he sample ange
p obabili ies (e.g.,
𝑝 a ge =[
10
−12,
10
−15]
). Such p ojec ion ca ies
some unce ain y, which exace ba es as we lowe he a ge p ob-
abili y and make i be a he away om he quan iles es ima ed
om he sample. The e o e, he sample size will de e mine how
low he p obabili ies can be o a obus es ima ion.
In o de o ind he
max𝑘
cu e o a small sample size we
need o es ima e quan iles wi hin he sample ange. In he case
o
𝑁=
100, o ins ance, we can choose quan iles a p obabili y
𝑝={
0
.
95
,
0
.
975
,
0
.
99
}
. Addi ionally, inding he smalles
max𝑘
ha
does no unde es ima e, in o de o p e en pessimism, equi es
boo s apping he sample o a obus es ima ion. We also in oduce
a change in he boo s ap sample size o
𝑛b=
10 wi h
𝑛boo sims =
100
boo s ap simula ions. Howe e , hose small sample sizes can lead
o signi ican a iance ac oss simula ions. We sol e his challenge
by making use o he Binomial lowe con idence in e al (LCI) [
9
] o
adjus he quan ile es ima ion. The binomial LCI akes in o accoun
how many da a poin s a e abo e he quan ile selec ed, and p o ides
a bound o he alue o he quan ile ha co ec s he lack o da a
Figu e 2: Compa ison o he scaled momen compu ed om
he sample momen es ima o o mul iple sample sizes o
a Weibull dis ibu ion o shape 𝛼=8and scale 𝜆=80.
poin s when he sample size is small. Applying he LCI allows us o
ob ain mo e consis en quan ile es ima es om sample o sample,
hence a oiding he impac o a iance ac oss simula ions. Finally,
he assessmen o do o he adap a ion o RESTK is whe he o
no he sample momen es ima o is s ill accu a e o small sample
sizes.
Momen es ima ion. When pe o ming es ima ions on unseen
ex eme quan iles, he sample size plays a key ole in de e mining
how us wo hy he es ima ion can be. A small sample size is no a
huge conce n when dealing wi h summa y s a is ics like he mean,
whe e i can be a gued ha
𝑁=
30 is enough o a good es ima ion
[
23
]. Es ima ing he momen s o a dis ibu ion om a sample is a
calcula ion ha has simila pe o mance in a small sample scena io.
High o de momen s, i.e. wi h high alue o
𝑘
, a e ac ually ha d
o es ima e e en wi h la ge amoun s o da a. MIK needs limi s o
he alue o
𝑘
because he sample momen es ima o in Equa ion
23 is no accu a e o high alues o
𝑘
. Tha is why he RESTK
me hodology is necessa y, o he wise, wi h Equa ion 23, MIK could
sa ely uppe -bound. On he posi i e side, o low alues o
𝑘
, he
momen s can be es ima ed sa is ac o ily wi h a small sample size. A
bigge sample size is use ul o ex emely high quan ile es ima ion
like
𝑝=
10
−15
, bu on much lowe quan iles, inc easing he sample
size may no p o ide wi h inc eased igh ness.
Example
. Le ’s assume a Weibull dis ibu ion o which we com-
pa e h ee sample sizes
𝑁={
100
,
1000
,
10000
}
. We compa e he
pe o mance o he sample momen es ima o o he momen s
be ween
𝑘=[
1
,
30
]
, which a he end-poin could be conside ed
high o de momen s. Fo each momen
𝑘
, we compu e he a io
be ween he sampled momen ,
ˆ
𝐸(𝑋𝑘)
, and he heo e ical momen ,
ha is he scaled momen
ˆ
𝐸(𝑋𝑘)/𝐸(𝑋𝑘)
, and compu e he bias.
Figu e 2 shows he mean scaled momen , which in ac shows he
ollowing: i) he sample momen es ima o pe o ms simila ly o
he wo highes sample sizes,
𝑁=
1000 and
𝑁=
10000, hence
showing ha , o momen s o ha o de , an inc eased sample size
does no p o ide mo e in o ma ion o his es ima ion. And ii), he
case o he smalles sample size
𝑁=
100 shows ha , while he e is a
sligh de ia ion in e ms o pe o mance, as he scaled momen o
high o de momen s is a ound 1
.
02, he pe o mance is sa is ac o y
compa ed o he highe sample sizes scena ios. Gi en ha he goal
o RESTK is o compensa e he inconsis ency o he sample momen
es ima o , RESTK can s ill be used o small sample sizes since he
a ge p obabili y is ela i ely high (e.g., 10
−6
), and hence, he alue
o 𝑘used in Equa ion 23 needed o such p obabili y is lowe .
5 Expe imen al E alua ion
In his Sec ion we compa e he adap ed e sion o RESTK in o-
duced in his wo k and he comp ehensi e se o EVT ins an ia ions,
adop ing di e en h eshold selec ion me hods.
5.1 Expe imen al Se up
In he e alua ion we include a syn he ic ep esen a i e se o uni-
modal and mix u e pa ame ic dis ibu ions (Sec ion 5.2), a ep e-
sen a i e ma ix mul iplica ion ke nel (Sec ion 5.3), as well as an
indus ial case s udy in he space domain (Sec ion 5.4), all execu -
ing on a ep esen a i e a ge ha dwa e, namely he NVIDIA AGX
O in [
35
]. While mul iple expe imen al se ups a e conside ed, hey
sha e some common con igu a ions. The sample size is ixed ac oss
all expe imen s in
𝑁 =
100. All samples collec ed ha e unde gone
an independence Ljung-box [
37
] es o ensu e he applicabili y o
EVT and Ma ko me hodologies. Fo all expe imen al scena io we
epo he bias, o expec ed alue, o each model showing he igh -
ness o he p o ided bound o he a ge 10
−6
o 10
−5
exceedance
p obabili y. Resul s a e epo ed o RESTK and EVT unde all
h eshold selec ion me hods add essed in Sec ion 3 (CV, QQ, QQB,
SP) wi h exponen ial (EXP) and GPD ligh ail (GLT) dis ibu ions.
5.2 Resul s: Syn he ic Dis ibu ions
Rep esen a i e Dis ibu ion Selec ion. I is sa e o assume ha
he a ge p og am will always e mina e in he con ex o iming
analysis o eal- ime p og ams, and hence, ha a WCET alue will
always exis uppe -bounding all concei able p og am uns [
54
].
The e o e, he ail o p og am’s execu ion ime execu ion is a ligh
dis ibu ion ha can be uppe -bounded by ligh and exponen ial
ail dis ibu ions [
28
,
36
,
49
]. Exponen ial ails can be ega ded as
pessimis ic in some cases [
54
], hus p o iding o a sa e uppe -
bound. Hea y ails ha e he cha ac e is ic o decaying slowe han
exponen ial ails. The e o e, hey a e ega ded as o e ly pessimis ic
o WCET pu poses and hey a e no e alua ed in ou wo k. I
is also he case ha he CDF o he execu ion ime o many p o-
g ams show se e al “peaks” usually ela ed o he cache le els,
wi h p og am’s execu ion ime a ying a ound hese peaks. This
esul s in he so-called mix u e dis ibu ions, which we co e wi h
a solid se o e e ence mul imodal (mix u e) dis ibu ions in acco -
dance o he s a e-o - he-a [
5
,
13
,
22
] wi h di e en ail p o iles
o inc ease ep esen a i eness: Gaussian, Weibull, and LogNo mal
a ian s wi h weigh s
𝑤 = {
0
.
8
,
0
.
2
}
. The unimodal and mix u e
Gaussian dis ibu ions p o ide di e en cases on exponen ial ails.
Simila ly he Weibull is used o ligh ailed scena ios, and inally
he Logno mal and Be a dis ibu ions a e used o be lexible in ail
beha io , anging om ligh ails o exponen ial ails depending on
he pa ame iza ion chosen. We show he analy ical o mula and
pa ame iza ion o each dis ibu ion, as shown in Table 1.
Expe imen al Resul s. As he e e ence g ound- u h alue
used o assess he model igh ness we use he heo e ically de-
ined quan ile unc ions o each pa ame ic dis ibu ion. Fo he
case-s udies, he quan ile needs o be compu ed om a bigge e -
e ence sample o
𝑁 e =
10
6
uns, which is only used o es ima e
he g ound- u h, o p oduce an es ima ion wi h g ea con idence.
Then we use he base quan ile unc ions o he R p og amming
Table 1: Uni- and mul i-modal dis ibu ions we use.
Unimodal dis ibu ions
Ac onym Family Pa ame e s P obabili y Densi y Func ion
(G)aussian Gaussian 𝜇=100,𝜎=10 1
𝜎√2𝜋exp −1
2𝑥−𝜇
𝜎2
(W)eibull Weibull 𝛼=4,𝜆=80 𝛼
𝜆𝑥
𝜆𝛼−1exp−𝑥
𝜆𝛼
(B)e a Be a 𝛼=8,𝛽=1/4𝑥𝛼−1(1−𝑥)𝛽−1Γ(𝛼+𝛽)
Γ(𝛼)Γ(𝛽)
Mix u e dis ibu ions wi h weigh s 𝑤={0.8,0.2}
Ac onym Family Pa ame e s P obabili y Densi y Func ion
(WM)ix u eWeibull 𝜆={100,150},Í2
𝑖=1𝑤𝑖𝛼
𝜆𝑖𝑥
𝜆𝑖𝛼−1exp−𝑥
𝜆𝑖𝛼
𝛼={8,8}
(GM)ix u e Gaussian 𝜇={100,120},Í2
𝑖=1
𝑤𝑖
𝜎√2𝜋exp−1
2𝑥−𝜇
𝜎2
𝜎={10,10}
(LNM)ix u eLogno mal 𝜇={5.0,5.1},Í2
𝑖=1𝑤𝑖1
𝑥𝜎𝑖√2𝜋exp−(ln𝑥−𝜇𝑖)2
2𝜎2
𝑖
𝜎={0.1,0.05}
language [
24
]. We also inc ease he con idence o he sample quan-
ile es ima ions by boo s apping he whole e e ence sample and
compu e he expec ed alue o he sample quan ile.
Unimodal dis ibu ions. In Figu e 3, we show he bias o each
model on he p edic ion o he quan ile wi h p obabili y
𝑝=
1
−
10
−6
.
The
G
and
W
dis ibu ions can be summa ized oge he as hey sha e
he same pa e n. The EXP models (CV, QQ, QQB, SP), end o be sa e
wi h he CV and SP being pessimis ic and he QQ and QBB being
ela i ely igh e . RESTK is he igh es model on he
G
case while
on he
W
is simila o he CV. GLT models end o unde es ima e in
gene al and changing he GLT model does no incu in signi ican
di e ence in he bias. The
B
case shows a di e en beha iou : he
CV is pessimis ic due o no being able o ind a p ope exponen ial
h eshold o his sample size, ins ead a ligh ail h eshold was
selec ed o he CV. All o he me hods excep he SP and RESTK a e
e y close o igh ness 1. While hese model could be conside ed
good pe o man s in o he domains, o eal iming analysis hey
a e deemed as op imis ic due o no uppe -bounding.
Mix u e dis ibu ions. Figu e 4 shows he bias o he mix u e
dis ibu ions. The pa e n o he biases is simila o he unimodal
cases. The EXP models show he same bias pa e n, wi h CV and SP
being mo e pessimis ic han QQ and QQB. The GLT show he same
beha iou o he
GM
and
WM
, bu o he
LNM
he GLT CV and SP a e
as igh as he QQ and QQB. Fo he pa ame ic dis ibu ions, we
ha e shown ha excep some pa icula cases, he GLT will always
end o unde es ima e in low sample scena ios, and hus a e no an
app op ia e model o WCET analysis. We also showed ha RESTK
ends o be he igh es model wi h EXP QQ and EXP QQB being
he second igh es models in gene al.
5.3 Resul s: Rep esen a i e Ke nel
In his sec ion we p esen expe imen al esul s o a ep esen a-
i e ke nel unning on he NVIDIA AGX O in [
35
]. The AGX O in
encompasses and ad ance MPSoC wi h complex compu ing ele-
men s, in e connec , and memo y con olle . All hese blocks cause
a iabili y in he execu ion ime ha align wi h he need o apply
p obabilis ic me hods.
We ha e analyzed edge applica ions wi h a ying eal- ime con-
s ain s, see Figu e 5. Da a om di e en senso s
1
○
a e ed in o
Figu e 3: Fi ing o unimodal dis ibu ions
Figu e 4: Fi ing o mul imodal dis ibu ions
applica ions
2
○
like ada applica ions, objec de ec ion, da a u-
sion, and na iga ion. Applica ions build on di e en ypes o neu al
ne wo ks (NN)
3
○
like ecu en and con olu ional. As MPSoCs
like he O in allow consolida ing se e al applica ions, he e can
be mul iple NNs ins ances unning on he CPU and accele a o s
4
○
. CPU is used when accele a o s a e busy o he wo king se is
educed and he o e heads o o load he ke nels (along wi h i s
da a) o he accele a o is oo high [
2
]. Fo ins ance ada -based ob-
jec de ec ion ha elies on small ma ices and LiDAR-based objec
de ec ion may ind accele a o s busy unning hea ie came a-based
objec de ec ion. Many o hese NN hea ily build on he ubiqui ous
ma ix mul iplica ion [
21
]
5
○
. I is ai o say ha ma ix mul iplica-
ion is he mos pe asi e ope a o o many AI applica ions ac oss
di e en domains. In ac , i has been show ha ma ix mul ipli-
ca ion accoun s o a la ge sha e o he execu ion ime (be ween
67% and 98.5%) ac oss deploymen s [
14
,
29
]. Fo ou expe imen s,
we conside wo a ian s o ma ix mul iplica ion, a basic one and
a iled e sion which will p oduce highe a iabili y due o i s
block-s uc u e unc ioning.
The wo le -mos cha s in Figu e 6 show he esul s o he
basic and iled ma ix mul iplica ion, espec i ely. The bias pa e n
in he unimodal and mix u e cases is also p esen in he ma ix
mul iplica ion ke nels. EXP CV and SP a e he mos pessimis ic
models wi h QQ and QQB being igh e , al hough RESTK is he
igh es one. All GLT models unde es ima e. Fo he iled ma ix
mul iplica ion all me hodologies excep RESTK a e ei he op imis ic
o oo close o igh ness 1 o be conside ed sa e o WCET.
5.4 Resul s: Space Case S udy
We expe imen ed wi h a spacec a au onomous na iga ion and
docking applica ion whe e an au onomous Guidance, Na iga ion
1
2
3
4
5
Rada , LiDAR, Came a
P edic ion, Fusion, Na iga ion, Rada
Con olu ional NN, Recu en NN
CPU, GPU, ...
Ma ix Mul iplica ion
Figu e 5: F om senso s/applica ions o ma ix mul iplica ion.
and Con ol (GNC) sys em is esponsible o acqui ing in o ma ion
om he spacec a asse senso s (came as, s a acke s, ine ia
measu emen uni s, e c.), assessing he posi ion and al i ude o
he spacec a , and issuing a speci ic maneu e . The au onomous
GNC deploys a deep lea ning model based on con olu ional neu al
ne wo ks o pe o m a docking manoeu e o an uncoope a i e
a ge (e.g., space s a ion) on a speci ic docking si e. Among he
unc ionali ies co e ed by he GNC, in ou expe imen s we ocused
on he pose es ima ion module. This componen akes images om
a monocula g ayscale came a o he a ge , and mus compu e i s
pose, ha is he ela i e posi ion and o a ion ( h ee dimensions
each) be ween he a ge and he chase . The pose module esul s
a e la e used o ajec o y planning and ac ua o s.
The model da a se comp ises o e 10K sa elli e dis ances and
con igu a ions, and di e se backg ounds ea u ing Ea h and a i-
ous ligh ing condi ions. The model is implemen ed on PyTho ch
en i onmen and has been ained using a ligh weigh a ian o
he Single Sho Mul iBox De ec o (SSD) [
55
], o e ing a good ade-
o be ween pe o mance and accu acy. The in e ence model is
execu ed on he O in AGX pla o m. I is wo h no ing ha he
applica ion hea ily builds on con olu ional neu al ne wo ks whose
execu ion is pe o med on he GPU.
We pe o m
𝑁 e =
10
6
uns, which ook weeks o execu e, in
o de o accu a ely es ima e he e e ence quan ile wi h p obabili y
𝑝=
10
−5
. Fo all EVT me hodologies and RESTK we used
𝑁=
100
and he same con igu a ion o he O in. In Figu e 6 ( igh cha ),
we show he esul s o he quan ile es ima ions. We obse e how
he space s udy shows he same pa e n, bu in his case EXP QQ
and QQB a e sligh ly unde es ima ing. RESTK is he igh es model
wi h EXP SP being a close second. GLT models show no di e en
pa e n and incu unde es ima ion also in he space s udy.
6 Rela ed Wo ks
Mul iple wo ks ha e ackled ex eme iming es ima es om a p o-
babilis ic pe spec i e, bu he majo i y o hem ha e no assessed
hei me hodologies o a small sample size. To he bes o ou
knowledge, he wo ks ha expe imen ed wi h a small sample size
a e he ollowing. The wo k on MBPTA-CV [
28
] sugges s a mini-
mum sample size o
𝑁=
100, al hough hei expe imen a ion was
done wi h
𝑁=
500. Sil a e al. [
50
] use a BM app oach wi h a
leas
𝑁=
150 samples in he expe imen s. Finally, Reghenzani
e al. [
46
] wo k owa ds selec ing a minimum sample size which
has enough s a is ical powe when pe o ming a goodness-o - i