Popular in Course
Popular in ComputerScienence
This 10 page Class Notes was uploaded by Betty Kertzmann on Tuesday September 22, 2015. The Class Notes belongs to CS 530 at Colorado State University taught by Yashwant Malaiya in Fall. Since its upload, it has received 46 views. For similar materials see /class/210183/cs-530-colorado-state-university in ComputerScienence at Colorado State University.
Reviews for Fault
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 09/22/15
Probability YKM Fault Tolerant Computing at r Odobcr 21 2008 1 u 3 Alu d saw Probabilistic Methods Much of this may be a review of probability and statistics you have taken elsewhere We cannot predict exactly when something will fail but we can calculate the probability of a failure and what can be done to reduce that This is similar to what insurance industry does they may not know when a person will die but they can compute lifeexpectancy of someone who is say 45 years old and maintains an ideal weight anber 21 2008 Fault Tolerant Computing 2 YlK Malaiya 10212008 Probability 10212008 Probabilistic Methods Overview We can have concrete numbers even in presence of uncertainty Topics Probability Disjoint events Statistical dependence Random variables and distributions Discrete distributions Binomial Poisson Continuous distributions Gaussian Exponential Stochastic processes Markov process Poisson process CW anber 21 2008 Fault Tolerant Computing 3 YK Malaiya r quotmenu Basics Probability of an event A n PA N if A occurs n times among N equally likely outcomes Probability is a number between 0 and 1 Ex Roll of a die P0dd 2 05 If more information is available probability of the same event changes If we know die is loaded perhaps P0dd 06 is possible 11 355quotquot 5 A October 21 2008 Fault Tolerant Computing 4 K Malaiya YKM 2 Probability 10212008 Basics Concepts Prob Of union of two events An 393 PAU B PAPB PA B Ex Roll of a die POutcome even U outcome S 3 Peven PS 3 Peven S 3 3 3 1 5 E E 7 E lfA and B are disjoint ie if AnB 4 Le empty set PAUB PA PB P K1PA October 21 2008 Fault Tolerant Computing 5 K Malaiya Conditional Probability Conditional probability PAIBIisthemr bahilwof39k igive n weknow B has39h a ppefneid P A B PA I B wforHB gt 0 PB lfA and B are independent PAB PA Then PA nB PA PB Example A toss of a coin is independent of the outcome of the previous toss lfA can be divided into disjoint Ai i1n then PBZPBAPA 1g October 21 2008 Fault Tolerant Computing 6 a Fif YiK Malaiya YKM 3 Probability YKM Random Variables A random variable rv may take a specific random value at a time For example X is a random variable that is the height of a randomly chosen student x is one specific value say 5 9 A random variable is defined by its density function A rv can be continuous or discrete continuous discrete i liliyn fi dx Px S X S x dx 1906 3umulative I A max 2 quot Foe l fxdx 212m 00 xmin llm1n Expected x max imax value mean J xfxdx Z xipxi xmin iimin W anber 21 2008 Fault Tolerant Computing Hmw l f YK Malaiya Distributions Binomial Dist Note that Ifxdx 1 2 pxi 1 Major distributions Discrete Bionomial Poisson Continuous Gaussian expomential 39 Binomial distribution outcome is either success or failure Prob of rsuccesses in n trials prob of one success being p n fr prl p r for r0n r Ineldentally quotCr r r n r W OWN 21 2008 Fault Tolerant Computing wjm AK Malaiya 10212008 Probability YKM Distributions Poisson Example Probabi Poisson also a discrete distribution 9 is a parameter fx xl Xe 1 l X u occurrence rate of something lity of r occurrences in time t is given by Often applied to fault arrivals in Sa system 1 I r f0 W0 Odommm a a uimmf39 YiK Malaiya Fault Tolerant Computing Distributions Gaussianwoer 39L a39pl ace di sc Overe d i tlb39e fOre Continuous Also termed Normal Gaus s ih391774ADl called Laplacian in France1774AD 0 0 standard 1 variance 40 50 00 70 80 90 uzmean 35 ye 102 Bellshaped curve 262 6 l oonSoo Density deviation which is Grades oaober 21 2008 Fault Tolerant Computing YiK Malaiya 10212008 Probability YKM Normal distribution 2 Tables for normal distribution are available often in terms of standardized variable zx ulo uo uo includes 683 of the area under the curve pi36 u3o includes 997 of the area under the curve Central Limit Theorem Sum ofa large number of independent random variables tends to have a normal d 39Str39 bUt39o n39 The reason Why itLi Sf abpliCabIei in man vic ases av October 21 2008 Fault Tolerant Computing 11 YK Malaiya Exponential amp Weibull Dist Exponential Distribution is a x continuous distribution Density function ft A e39 M 0lttsoo Example 9 exit or failure rate l 1 Prexit the good state during t tdt e 1 e39 M dt g i The time T spent in good state has om i an exponential distribution 1 Weibull Distribution is a 2 0 W parameter generalization of mm exponential distribution Used when betterfit is needed but is more complex October 21 2008 Fault Tolerant Computing 12 K Malaiya gym itquot A 10212008 Probability YKM Variance amp Covariance Variance a measure of spread VarX EtXuxr Standard deviation Varx 2 o standard deviation usually for normal dist Covariance a measure of statistical dependence Covth EXuxYuy1 Correlation coefficient normalized pXy CovXYI ox 6y Note that 0ltpxylt1 October 21 2008 Fault Tolerant Computing 13 K Malaiya Stochastic Processes Stochastic process that takes random values at different times Can be continuous time or discrete time Markov process discretestate continuous time process Transition probability from state i to state depends only on state i It is memoryless Markov chain discretestate discrete time process Poisson process is a Markov counting process Nt t2 0 such that Nt is the number of arrivals up to time t 1 October 21 2008 Fault Tolerant Computing 14 a Ff YK Malaiya 10212008 Probability YKM Poisson Process properties Poisson process A Markov counting process Nt t2 0 Nt is the number of arrivals up to time t Properties ofa Poisson process N00 Pan arrival in time At Mt No simultaneous arrivals We will next see an important example Assuming that arrivals are occurring at rate 7 we will calculate probability of n arrivals in time t a Odober 21 2008 l Nihilw 39 Fault Tolerant Computing 15 YlK Malaiya Poisson process analysis A process is in state I if I arrivals have occurred Pit is the probability the process is in state i A A In state i probability is flowing in from state M and is flowing out to state i1 in both cases governed by the rate 7t 9 A i arrivals Thus dB 0 dt 1Pt t 21110 n 01 We ll Solve itf lrst 39fOr Pratt Odobcr 21 2008 11 itquot 5 A Fault Tolerant Computin then for YlK Malaiya 10212008 Probability YKM Poisson process Solution for P0t i arrivals R P process in state 0 SOZWiOn 3 PotAlPot1Mt 1nltP0ltrgtgt zrc 1 t RIAt Rtmt PotC2e At Since 1000 1 C2 1 dP t t 0 quot21 2008 Fault Tolerant Competing 17 Y K Malalya Poisson Process General solution W dt l e nee 0 so ve U t uDHQ n 01 Using the expression for Pot we can solve it for P1t Solving recursivelywe get 11 n 1 WhichWei kn39owi39s 7120919 1 A l Poisson distribution ig October 21 2008 Fault Tolerant Computing 18 a 53 YlK Malaiya 10212008 Probability YKM Poisson Process Time between Two Events Here we ll show that the time to next arrival is exponentially distributed 39th 39 39 39 I arrlval 1th arrlval Pti1 gt t Pn0 arrival in ti ti t e l Thus the cumulative distribution function cdf is given by Ft P0 ST St 21 Since the density function is derivative of cdf differentiating both sides we get f0 M Exponential39dismbutipn CW Odober 21 2008 Fault Tolerant Computing 19 a YiK Malaiya r unawv 10212008 10