哈尔滨工业大学计算机网络4SimulateP2HIT2017

SIMULATION:DataAnalysisComparisonsofthemodeloutputtotherealsystem

todevelopanacceptablelevelofconfidencethattheperformancemeasurespredictedbythemodelisapplicabletotherealsystemifamodelfailstoreproducethebehaviorofthesystemunderexistingenvironment,onecanhardlyexpectittogivemeaningfulpredictionsundernewenvironments

TypicalMethod

EstimatethemodelparametersRunsimulationprogramwiththeestimatedparametervaluesandcollectdataforthedesiredperformancemeasuresVerifythatthedatacollectedfromthesimulationrunsareconsistentwiththosemeasuredintherealsystem

INPUTANALYSISRealWorldOutputInputSimulationSimulationModelInputOutput

ValidinputtoasimulationmodelgivingunrealisticoutputimpliesaninvalidsimulationmodelValidsimulationinputassistsinsimulationmodelvalidation

NeedforEstimation

Real-worldsystemislikedablackboxconcealingfixedunknownssuchasmeanpacketservicetime,meaninter-arrivaltime,etc.Needtodetermineunknownsatsomelevelofaccuracytosimulatereal-worldsystem,i.e.needsestimationUsedatafromthesystemtofindestimatesofunknownsEstimatesofunknownswillrepresentunknownsinsimulationExample:toestimatethemeanservicetimeinasystem,wemaychoose

Thesmallestservicetimeinasample

Arithmeticaverageofservicetimesinasample

Convention:ifistheunknownmeanservicetime,is

ˆoftenusedasanestimateof

GeneralpropertiesofEstimates

Estimatesarerandomvariables;hence,estimateshave

Probabilitydensityfunctions(p.d.f.s)

Meansandvariance

Ingeneral,anestimatehavingasmallervarianceisbetterp.d.f.forXˆ1p.d.f.forXˆ2

Intheaboveexample,bothandareestimatesofanXˆ1Xˆ2unknownparameterTheestimateismorelikelytogiveawiderrangeofXˆ1valuesthanisXˆ

Thevarianceofisgreaterthanthevarianceof2XˆXˆ2

Hence,theestimateisabetterestimatethantheXˆ2Xˆ11estimateBiasedandUnbiasedEstimates

Whentheexpectedvalueofanestimatecoincideswiththeparameterbeingestimated,theestimateisdefinedasanunbiasedestimateoftheparameterIftheestimateisnotunbiased,itisdefinedasabiasedestimateHowever,asmallvarianceforanestimateisusuallythemostimportantconsiderationindeterminingtheestimateofchoicewhenthebiasintheestimateisnotverylarge

p.d.f.forp.d.f.forXˆ3Xˆ4bias

ˆexpectedvalueofXˆ4expectedvalueofX3MaximumLikelihoodEstimates(MLE)

ThemostpopularwayinestimatingunknownparametersusingasampleofdataifaspecificprobabilityfunctionisassumedMLEproducesestimateswithsmallvariance,i.e.maximizingthelikelihood(probability)oftheestimateshavingthevaluesoftheunknownparameters

MLEProperties

MLEisunbiasedandnormallydistributed,andhasthesmallestvarianceofallestimatesforverylargesamplesizes

IfMLEisunbiasedforanysamplesize,ithasthesmallestvarianceofallpossibleestimatesfromthegivensamplesize,i.e.itisthebestofallbiasedandunbiasedestimatespossiblePropertiesofEstimates

IfW1,Wvariablesfromagivensystemwithmeanwaitingtime

,thenE(Wi)=

foralli=1,2,…,n,implyingWiisanunbiasedestimatedofforalliIfwedefinetheestimate2,…,Wnarenindependentwaitingtimerandom

ˆ1nW

Wini1thenandisalsoanunbiasedestimateEWˆWˆof

Q:usingtheaverageortheindividualW?

Ifvarianceofthewaitingtimeinsystemis2,thenVar(Wi)=

2foralliˆ1n

Var()=varianceofW

Winni1nvar(n1

wi)n12var(

wi)n12(var(w1w2...wn))i1i112

2

n2(n)n

Asˆ

22Var(W)Var(Wi)nthearithmeticaverageisabetterestimatethananyofWˆtheindividualwaitingtimesWiRecognisingUnderlyingDistributions

Oneoftheimportantaspectstounderstandaboutinputtoareal-worldsystemiswhatprobabilitydistributionfunctionbestrepresentstheinputforsimulationpurposes.Weneedtoidentifyatheoreticalprobabilitydistributionthatmatches,inastatisticalsense,real-worldbehaviorssuchasinter-arrivalandservicepatterns.

probabilitydistributionsusedinsimulationmodelsareusuallydeterminedfromhistorical/observeddata

Approach:assumesometheoreticaldistributionandcompareitwithrepresentativereal-worlddata

Ifthedifferencebetweenthereal-worldandtheassumedtheoreticalistoolarge,rejectthetheoreticaldistribution

Determineiftheprob.dist.chosenisvalidbyusing"goodness-of-fit"testUniformf(x)0abxExponentialf(x)xHyperexponentialErlangf(x)f(x)xxNormalf(x)xChi-Square(2)test

Basedontheobserveddata,generateahistogramwithkgroupswithfrequencyingroupi,Oi,beingthenumberofobservationsininterval[ai-1,ai)YoumaystartwithNequalintervals(however,intervalsneednotnecessarytobethesamesize)Thenumberofgroups,N,canbedeterminedasfollow:

SamplesizeN(n)2050Don’tuseChi-squaretest5to1010010to20>100nton/5

let[ai-1,ai)betheboundariesofcelli(i.e.putsampledatainNgroups)

letf(t)bethehypothesizedtheoreticalprob.densityfunctionletnbetheno.ofsamplepoints

frequencyEinf(t)Oiai-1aiInter-arrivaltimethen

thetheoreticalfreq.incelliisaiEinpin

ai1f(x)dxi1,2,...,N

Theteststatisticsischi-squaredistribution2N(OiEi)2ˆ

i1Eiwithdegreeoffreedomdf=N-m-1wheremistheno.ofparameterestimatedfromthedataandEiistheobservedfrequencyincelli

ifthecomputedvalueofˆ2islessthanthatfromtheChi-squaretable,wewillacceptthehypothesisthattheprob.dist.chosenisvalidatacertainconfidencelevel

Note:itisrecommendedthattheexpectedfrequencyEiincellicontainnolessthan5points.

IfEi<5foranyi,grouptwoormoregroupssothatallEi’s5

RecalculateOiforalliifre-groupingisneededExample

Observed800packetsarriveover100secondsAssumethatthearrivalprocessisPoisson

n

eProb{npacketsarrivedinasec}=Pnwheren=0,1,2,…,andisthetheoreticalmeanno.n!ofpacketsarrivingpersec.

isestimatedas800/100=8Fromtheobservation,9groupshasbeendecidedEiiscalculatedasfollow:

E.g.theintervalforE4is[7,8)10087e8E4100P(7)13.967!

Theresultissummarizedasfollow:Groupi123456789IntervaliOiEi[0,5)[5,6)[6,7)[7,8)[8,9)[9,10)[10,11)[11,12)[12,)6111014121979129.969.1612.213.9613.912.419.937.2211.1916(OiEi)2Ei1.580.370.400.0000.273.500.860.440.0581

Fromtheabove,wehave9(OiEi)27.485

Ei1i

Thedegreeoffreedom=N-m-1=9-1-1=7withm=1aswehaveestimatedoneunknownparameterWith=0.05,=14.1>7.485,wecannotrejectthat

2,7thereal-worldprocessisPoisson

WeconcludethatinputarrivalprocessisPoissonK-Stest

NamedafterstatisticiansA.N.Kolmogorovin1933andN.V.Smirnovin1939.

K-Stestallowsonetotestifagivensampleofnobservationsisfromaspecifiedcontinuousdistribution.

BasedontheobservationthatthedifferencebetweentheobservedCDFFo(X)andtheexpectedCDFFe(X)shouldbesmall.K-STest

ThesymbolsbelowdenotethemaximumobserveddeviationsaboveandbelowtheexpectedCDFinasampleofsizen:K

nmaxx[Fo(x)Fe(x)]K

nmaxx[Fe(x)Fo(x)]

IfK+andK-aresmallerthan,K[1;n]listedinK-Sdistribution,theobservationaresaidtocomefromthespecifieddistributionatthelevelofsignificance.K-STest

Fromrandomnumbersdistributeduniformlybetween0and1,theexpectedCDFisFe(X)X

andifxisgreaterthanj-1otherobservationsinasampleofnobservations,thentheobservedCDFis.Therefore,toFo(x)J/ntestwhetherasampleofnrandomnumberisfromauniformdistribution,firstsorttheobservationinanincreasingorder.Letthesortednumbersbe{x1,x2,…xn}suchthatXn-1<Xn.Then:K

nmax(njxj)j

K

nmax(xj

jn1)jK-STest

E.g.Thirtyrandomnumbersaregeneratedusingaseedof15inthefollowingLCG:Xn=3Xn-1mod31,thenumbersare14,11,2,6,18,23,7,21,1,3,9,27,19,26,16,17,20,29,25,13,8,24,10,30,28,22,4,12,5,15.

Thenormalizednumbersobtainedbydividingthesequenceby31,thensortthem.Jfrom1to30,wehaveXjasfollowing:0.03226,0.06425,0.09677,0.12903,0.16129,0.19355,0.22581,0.25806,0.29032,0.32258,0.35484,0.38710,0.41935,0.45161,0.48387,0.51613,0.54839,0.58065,0.61290,0.64516,0.67742,0.70968,0.74194,0.77419,0.80645,0.83871,0.87097,0.90323,0.93548,0.96774K-STest

Thecorresponding(j/n–Xj)and(Xj–(j-1)/n)canbecalculatedaccordingtodifferentvalueofj.K-Sstatisticscanbecomputedasfollows:K

nmaxj(njxj)300.032260.1767K

nmaxj(xj

jn1)300.032260.1767

SinceK[0.9,30]forn=30and=0.1,is1.0424.HencebothK+andK-arelessthanthevaluefromtable,therandomnumbersequencepassestheK-Stestatthislevelofsignificance.TestingComparison

K-Stestisspecificallydesignedforsmallsamplesandcontinuousdistributions.Thisisoppositeofthechi-squaretest.

K-Stestisbasedonthedifferencebetweenobservedandexpectedcumulativeprobabilities(CDFs)whilethechi-squaretestisbasedonthedifferencesbetweenobservedandhypothesizedprobabilities(Pdf’s).

K-Stestuseseachobservationinthesamplewithoutanygrouping,whilechi-squaretestrequires.Inthissense,aK-Stestmakesbetteruseofthedata.Oneoftheproblemsinusingchi-squaretestisproperselectionofthecellboundaries.OUTPUTANALYSISWhenanalyzingstatisticaldata,usuallyassume:

thesamplesareindependenttheprocessistimeinvariantwhenthesamplesizeislarge(>30),thesamplemeanisanormallydistributedrandomvariable

Indiscreteeventsimulation,theaboveassumptionsaregenerallynottrue.

Here,thewaitingtimesofjobsarehighlyseriallycorrelated.

Oncethewaitinglinebuildsup,everyjobsjoiningthelinefacesalongwait

Conversely,duringtheperiodsoftimewhenthereisasmallornowaitingline,allarrivalswaitforshortperiods,ordonotwaitatall.

Hence,thestandardstatisticalshouldnotbeapplieddirectly.

However,sometimes,ourinterestistocomparetwosimulationresultssoastoevaluatealternativepolicies.

Here,preciseestimateofoutputvaluesisunnecessary.Therearetwotypesofoutput

Observationbased

E.g.waitingtimesofncustomers,wi,i=1,…,n

NeedtodetermineE(W)and

W2waitingtimecustomer

Time-weighted1n2no.

E.g.queuelengthin0tT

NeedtodetermineE(Q)and

Q2queuelengthtime

Forobservationbasedoutput,themeanandthevarianceofwaitingtimeare:ˆ1nW

wini1andn21ˆ2s

(wiW)n1i1wherewiistheithjobwaitingtime

WˆisanunbiasedpointestimatorofE(W)sinceWˆE()=E(W)s2isanunbiasedpointestimatorofsinceE(s2)=

W2

W2

Fortime-weightedoutput:Q3Q5Q2Q4Q6Q1queuelengthtimeTt1t2t3t4t5t666626

Qiti

Qiti

QiQˆti

Qi2ti

Qˆi1

i1s2

i1

i1Qˆ26tTTT

ii1

NotethatisanunbiasedpointestimatorofE(QˆQ)sinceE()=E(QˆQ)However,s2isabiasedpointestimatorofsinceE(

Q2sQ22)

Example32queuelength1time293578Qˆ11221322231219192.1192s2112222132222232122119994519219250.5432999ConfidenceIntervalEstimation

aˆbW

istheprobabilityofrejectingagoodmodelFindaandbsuchthatProb{aE()Wˆb}=1-A100(1-)%confidenceintervalforE()=E(W)is[a,b]WˆIngeneral,theinterval[a,b]ismoreusefulthanthepointestimateWˆ

whenthevarianceofthepointestimatorislargeRecall

E()=E(WˆW)E(s2)=

W2Var()=Wˆs2/n

ItcanbeshownthatWˆE(W)s/napproximatelyfollowsthetdistributionwithn-1degreesoffreedomt-distribution

-t0.025,n-1

t0.025,n-1

Forsamplesizen=6,C.I.=[-2.571,2.571]=2.571)Forsamplesizen=11,C.I.=[-2.228,2.228]2.228)(t0.025,5

(t0.025,10=

Forthesameconfidencelevel,alargersamplesizegivesanarrowerrangeConfidenceIntervalGeneration

-t/2,n-1

t/2,n-1P

t/2,n1

tt/2,n11WˆE(W)P

t/2,n1

t/2,n1

PWˆt/2,n1s/nE(W)Wˆt/2,n1s/ns/n

The100(1-)%confidenceintervalforE(W)isWˆt/2,n1s/n,Wˆt/2,n1s/nExample

Samplesize=6Sampleaveragewaitingtime=10secStandarddeviationofthewaitingtime=4secThe95%confidenceintervalforthemeanwaitingtimeE(W)is

2.57142.571410,1066thatis[5.8,14.2]sec(Note:t0.025,5=2.571)Example

11differentqueuelengthshavebeenobservedataswitchduringaperiodTSamplequeuelengthtime-weightedaverage=20packetsSamplequeuelengthtime-weightedstandarddeviation=3packets

The95%confidenceintervalforthemeanqueuelengthE(Q)is2.22832.228320,201111thatis[17.98,22.02]packets(Note:t0.025,10=2.228)TerminatingVs.Non-terminatingSystems

discrete-eventsystemscanbecategorizedasbeingeitherterminatingornon-terminatingrequiresdifferentoutputanalysismethods

TerminatingSystems:

EventsthatdrivethesystemstopoccurringatsomepointintimeTheremaybereoccurringcycle,buteachcyclestartsofffreshTheendstateofonecyclewillnotaffectthestartingstateofthenextcycle,i.e.eachcycleisindependentfromtheothersE.g.

BankAcomputersystemthatoperatesbetween8a.m.and10p.m.everydayTwogamblerstosscoins

Non-terminatingSystems:

EventsoccurindefinitelyAsinglecyclewillcontinueindefinitelyandthereisnoterminatingeventE.g.

Jobshop

Airport

HospitalTransientandSteady-StatePropertiesIngeneral,aterminatingsystemmaynotbeabletoreachthesteadystate

however,thisisnotalwaystrue!!!Lets(t)=systemstateattPs(t)=Prob.thatthesystemisinstatesattimetthenthesystemisinsteadystaterelativetostatevariablesifdPs(t)0dtotherwisethesystemisintransientstateNote:Insteadystate,thesystemwillstillswitchfromstatetostateasinthetransientphase;however,itisthestatevariable'sprobabilitydistributiongetsstabilizedovertimeExamples:Systemsthatcanachievesteadystate:

Ajobshopreceivesordersataconstantmeanrate.

Non-terminatingandcanachievesteadystate

Highwaytollboothsduringrushhour(7a.m.to9a.m.)

ifthetrafficintensitydoesnotchangeoverthe2hours,andthearrivalrateissubstantial,thesystemwillpassthroughitstransientphaseveryquickly

aterminatingsystemSystemsthatwillnotachievesteadystate:

Ahealthcenterthatschedulesthenumberofphysicianstoreflectthepatientarrivingpatternthroughoutthe24-hourday.

Non-terminating

canneverreachthesteadystatebecausethepatientarrivalmeanrateandthenumberofphysicianskeepchanging

Usersofatime-sharedcomputersystemconnecttothesystembetween8a.m.and5p.m.

terminating

cannotachievesteadystatebecausetherateatwhichusersconnecttothesystemvariesthroughoutthedayIngeneral,

interminatingsystem,weareinterestedinthetransientbehaviorinnon-terminatingsystem,weareinterestedinthesteadystatebehavior

OutputAnalysisforTerminatingSystemRecall:1nX

xini1and21n2s

(xiX)n1i1whereobservationsxiareINDEPENDENT.(why(n-1)notn?Thesumofallndifferencesare0?)REPLICATIONmethod:

usedtoensurethattheobservationsareindependent;thesimulationisexecutedanumberoftimes,witheachreplicationindependentoftheothers;ForasimulationreplicatedRtimes,withniobservationsinthei-thsimulation,let

Wij=j-thobservationofthewaitingtimeonthei-threplicationwherei=1,2,...,Randj=1,2,...,niandQi(t)bethequeuelengthobservedattimetforthei-threplication,where0t

TForeachreplication,wehaveˆ1niWin

Wijij1and1TQˆiQi(t)dtT

t0Theestimatesforthesystemare:ˆ1RˆWR

Wii1ˆ1RˆQR

Qii1ThevarianceofWandQaregivenby1R2sw2

WˆiWˆsQ2

QˆiQˆR1i11R2R1i1Confidenceintervals:WˆE(W)QˆE(Q)andsw/RsQ/RaretstatisticswithR-1degreesoffreedomThe100(1-)%CIforE(W)isˆsWˆsW

Wt/2,R1,Wt/2,R1

RRThe100(1-)%CIforE(Q)isˆsQˆsQ

Qt/2,R1,Qt/2,R1

RR

Forterminatingsystem,weareinterestedinthetransientbehavioraswellForeachreplication,observationsaremadeatdesignatedpointsintimeorupontheoccurrenceofdesignatedevents.

ForasimulationreplicatedRtimes,withKintermediateobservationsineachsimulation,letxij=j-thobservationonthei-threplicationwherei=1,2,...,Randj=1,2,...,KLetyi=someoverallperformancemeasureduringthei-threplicationthen1RXjR

xijj1,2,...,Ki121R2sj

(xijXj)R1i1and1R21R2Y

yisy

(yiY)Ri1R1i1TheconfidenceintervalsforE(xij)andE(yi)aresjP(jXjt/2,(R1))1RandsYP(YYt/2,(R1))1RHence,thehalfwidthoftheconfidenceintervalissIt/2,(R1)RTruncation

TransientRemoval:Intruncation,thevariabilityismeasuredintermsofrange–theminimumandmaximumofobservations.

Givingasampleofnobservations{x1,x2,..xn},thetruncationmethodconsistsofignoringthefirstLobservationsandthencalculatingtheminimumandmaximumoftheremainingn-Lobservations.

ThisstepisrepeatedforL=1,2,..(n-1)untilthe(L+1)thobservationisneithertheminimumnormaximumoftheremainingobservations.Truncation

E.g,considerthefollowingsequenceofobservations:1,2,3,4,5,6,7,8,9,10,11,10,9,10,11,10,9,10,11,10,9…

Ignoringthefirstobservation,theremainingis(2,11).Sincethesecondobservationisequaltotheminimum,2.Thetransientphaseislongerthan1.GoaheadwithL=2,3,..OutputAnalysisforNon-terminatingSystemsProblems:

CovariancebetweenSamples

setsofdatagatheredaregenerallynotindependent

varianceestimateswillbebiased

RunLength

Althoughthesystemitselfmaybenon-terminating,thesimulationmusteventuallybeterminated.

Ifsystemterminatedtooearly,maynothavearepresentativesimulation

Impracticaltomakeextremelylongrunforverycomplexsystem

InitialConditionBias

veryoftensimulationrunsareinitiatedwiththesysteminanIDLEstatewithnojobsinthesystem

NOTrepresentativeofastateusuallyencounteredduringnormaloperationofthesystem

outputmayundergolargefluctuationsbeforeachievingSteadyState

i.e.thecurrentbehaviorisindependentofitsstartinginitialconditionsandtheprobabilityofbeinginoneofitsstatesisgivenbyafixedprobabilityfunction

Note:theindividualbehaviorswillcontinuetoshowtheirinherentvariability,butthevariationsofthesamplemeanwillbalanceout

thesamplemeanthatincludesearlyarrivalswillbebiasedifourinterestistoestimatethesteadystateperformance

Methodstoreducetheinitialbias

StartthesimulationinIDLEstateandrunforasufficientlylongperiodoftime

theeffectofbiasonestimatesofmeanandvarianceisnegligiblysmall

Startthesimulationnearertothesteadystate

e.g.steadystateobtainedinthepreviousruns

Runsimulationforaperiodoftimecalled"WARMING-UPPeriod"

duringwhichnostatisticsarecollected(orcollectedstatisticsarediscarded)

startcollectingstatisticsattheendofthewarming-upperiod

problem:mustdecidewhensteadystateconditionsbeginReplicationofSimulationRuns

similartotheoneusedforterminatingsystemsmustavoid(orminimize)theeffectoftheinitialconditionstheestimationofsamplemeanandvariancerequiresindependentsamples

repeatsimulationRtimesforthesamesamplesizewiththesamestartingconditions,butwithdifferentstreamsofrandomnumbers

thesamplemeanisgivenbytheoverallmeanoftheRreplications

letxijbethej-thobservationinthei-thruntheestimatesofthemeanwaitingtimeanditsvarianceforlargeRare

ˆs2var(X)

xˆiXˆ1R1niX

xˆiwherexˆi

xijRi1nij112R1where=meanofthexˆii-thrunproblemwithusingthismethod:

highcomputationcostforrepeatingtheinitialwarmupperiodandtheuncertaintyofthelengthphaseofthetransient

BiascannotberemovedbyaddingreplicationsExample:ThefollowingshowsthequeuingdelayofpacketsExperimentPacketNo.ˆNo.12345678Wi123450.040.120.080.080.130.110.090.120.150.090.070.130.140.090.110.060.130.060.150.120.060.080.070.10140.10250.10.140.130.060.090.10.10.10.080.070.093750.091670.070.10.11Theaveragequeuingdelayisˆ15ˆW5

Wi0.09786seci1andvariance152s2

WˆiWˆ2.3461054i1Fora95%confidenceinterval,=0.05t/2,4=t0.025,4=2.776The95%confidenceintervalforthequeuingdelayisˆsWt0.025,4nˆ0.0048441.5318W2.7761.5318Wˆ0.0060130.097860.006013

0.09185,0.10387secBatchMean

Asimulationisrunforalongperiodoftime,anditsoutputisdividedintoBATCHESofequalsize

i.e.periodicallyrecordandthenresetthestatisticalmeasures

IftheBatchLengthissufficientlylong

theindividualbatchescanbetreatedasindependentsamples

samplemeanandvariancecanbecomputed

theinitialbiasneedstobeeliminatedonlyonceatthebeginningofthesimulationbydiscardingthefirstfewbatches

theassumptionthattheindividualbatchesareindependentisnotstrictlytrue

thefinalstateofabatchbecomestheinitialstateofthenextbatch

autocorrelationexists

toreducetheautocorrelation,consecutivebatchesareseparatedbyintervalsinwhichtheoutputsfromthesimulationarediscarded

problem:

nosimpleformulatodeterminethebatchsizeandthelengthoftheintervalseparatingconsecutivebatches

Note:WecandetermineifthebatchesareindependentbyusingtheRUNSTEST.RUNSTEST

Thetestisbasedonthenumberofascendinganddescendingruns,indicatedbythesignofthedifferencebetweensuccessiveelementsinthesample.TestthehypothesisH0:theoccurrenceoftheobservationsareindependent.

E.g.Thesignofthedifferencesforthefollowingare:10.1,12.2,9.7,6.1,4.2,5.9,6.8,5.5+---++-1234thusgiving2runsupand2runsdown,i.e.totalof4runsLetR=totalnumberofrunsIftherearenindependentobservations,thenE(R)=(2n-1)/3andVar(R)=(16n-29)/90E.g.R=28,n=40E(R)=26.3Var(R)=6.78NormalizingR,wegetRERZ

R=(28-26.3)/2.60=.65WhenZiscomparedtothecriticalvalueofZ.05=1.96,wecannotrejectH0.RegenerativeMethod

RegenerativeSystems:systemswhereidenticalstatesrecuratrandomintervalsoftime

i.e.thesystemREGENERATESitselfatrandomintervalsintime

Regenerationpoint:thetimeatwhichthesystemstatesrecur

theregenerationpointsarecomputedwithrespecttoaparticularsetofvaluesofsystemvariableschosenasreferencepoint

isasystemstateinwhichthefuturebehaviorofthesystemisindependentofthesystem'spasthistory

e.g.whentherearenojobsqueuingorbeingservedandtheserverisidlecanbeusedasareferencepoint

Regenerativecycle:theintervalbetweentworegenerationpoints

duringwhich,thenumberofactivitiestakingplaceinthesimulationmayvary

Note:Itispossiblethatevenifregenerationpointsexists,theparametersofthesystemmaybesuchthatitneverreachesthem

e.g.Inasingle-serverqueuingsystemwherejobsarriveat3/minandeachtakesonaverage1mintoserve,thesystemmayneverreachtheidlestateagain.

Toillustrate,forthei-thcycle,toestimatethesystem'spropertyXusingtheratiooftworandomvariablesYiandTi,suchthatE(X)=E(Y)/E(T)whereX=meanjobwaitingtimeY=totalwaitingtimeofalljobsduringcycleT=No.ofjobsarrivingincycleLetn=no.ofcycleobservednYinTiT

Y

i1ni1nandYXTthenTogettheconfidenceintervalonE(X),letDi=Yi-E(X)TiandVar(D)=Var(Y)+E(X)2Var(T)-2E(X)Cov(Y,T)thenz/2P(E(X)X)1Var(D)/nwhere1nnCov(Y,T)n1

YiTin1YTi1OutputValidation

Wecomparemodeloutputwithreal-worldsystemoutputwhenmodelandsysteminputaresimilarModelModelInputModelOutputSimilarCompareSystemReal-SystemInputWorldOutputSystemHypothesisTesting

usefulintestingiftwomeansobtainedfromdifferentsimulationenvironmentsaresignificantlydifferentinthestatisticalsense

observationsmustbeindependentandmustbedrawnfromanormalpopulationTheElementsofaStatisticalTest

NullHypothesis,Ho

thehypothesistobetested

AlternativeHypothesis,Ha

thehypothesistobeacceptedincaseHoisrejected

TestStatistic

afunctionofthesamplemeasurementsuponwhichthestatisticaldecisionwillbebased

Rejection(orCritical)Region

ifthecomputedvalueoftheteststatisticfallsintherejectionregion,werejectthenullhypothesisDefn.:TypeIerror-rejectionofHowhenHoistrue-prob.ofatypeIerrorSimplecase:comparethemeanwithaspecificvalueNullhypothesis:Ho:µ=µ0Alternativehypothesis:A1:µµ0A2:µ>µ0A3:µ<µ0whereµ0isaspecifiedvalue.

acceptorrejectthenullhypothesisusingt-testwithn-1degreeoffreedom(sissamplevariance)x0t0

s/n

letbethedesiredlevelofsignificance(0<<1),andtn-1,asthecriticalvalueofthet-distributionsuchthatP(t>tn-1,)=

conditionforrejectingthenullhypothesis:acceptingconditionforalternativehypothesisrejectingHoA1:µµ0|t0|>tn-1,/2A2:µ>µ0A3:µ<µ0t0>tn-1,t0<-tn-1,E.g.Fromanexistingsystem,themeasuredmeanwaitingtime=µ0Fromasimulationmodel,xnmeanwaitingtimesarecollectedSamplemean=Samplevariance=s2Populationme