PACIFIC COMP 155 - States and Events Random Numbers

Unformatted text preview:

COMP155Computer SimulationSeptember 8, 2008States and Events A state is a condition of a system at some point in time An event is something that cause a system to shift from one state to anothershift from one state to anotherLast Time FSA: Finite State Automata event driven transitions Markov Modelsprobabalistictransitionsprobabalistictransitions Production Systems rule based transitionsConditions and EventsConditions and EventsPetri Netstokensplaces transitionstokensPetri Nets Places are conditions Transitions are events Transitions can fire if all incoming places have a tokenif all incoming places have a token Firing a transition results in a token in all outgoing placesPetri Netst1 and t2 areready to firePetri Netst3 is ready to firePetri Netssystem is idleInputs to Petri Nets Some places can be designated as inputs May be a time-based function for adding tokens May be an infinite source of tokensA Manufacturing LineManufacturing Line: Petri NetMutex - Semaphorecriticalcriticalsemaphorecriticalsectioncriticalsectionhttp://www.cs.adelaide.edu.au/users/esser/mutual.htmlModeling UncertaintyModeling UncertaintyProbabilistic Processes Many of the parameters in real-world systems are probabilistic rather than deterministic To simulate these parameters, we need random number generatorswe need random number generatorsExample: Single Queue Checkout Consider the following functional model for a single-queue of customers (i.e., a 7-11)KQBlock K is the source of customer arrivals.Block Q is the queue of customers. Customers enter the queue immediately upon arrival and exit after checkout.Both of these blocks should be replaced by probabilistic functions.KQExample: Single Queue Checkout Sources of Randomness: Customer Arrival: time between customer arrivals Checkout: time required to checkout Although random, Although random, both times can be described statistically by probability distributions (PDs) To model the system, we need to: determine the PD from the real systems replicate the PD with appropriate random numbersProbability Distributions A probability distribution describes  the range of possible values that a random variable can attain, and theprobabilitythat the value of the random theprobabilitythat the value of the random variable is within any subset of that range Probability distributions may be: continuous: allowing for all values in a range (real numbers) discrete: allowing for particular values in a range(integers)Uniform Distributions A uniform distribution is one in which the probability of any of the possible values is the same.Example: The time between arrivals of Example: The time between arrivals of customers is uniformly distributed over the range [1, 10] minutes.Uniform Distribution: DiscreteprobabilityIf we only allow for integer values in [1,10], then the probability of any one of those values is 10%.10%1 2 3 4 5 6 7 8 9 10arrival interval (minutes)Sum of probabilities must be 1.0 (100%)Uniform Distribution: ContinuousprobabilityIf we allow for all real values in [1,10], we have a continuous probability distribution.1 2 3 4 5 6 7 8 9 10arrival interval (minutes)Area under the curve must be 1.0 (100%)11.11%Non-uniform Distributions Non-uniform distributions are described by functions, such as the familiar bell-shaped Gaussian distribution:likely valuesunlikely valuesDiscrete Random Variables If the number of possible values for X is finite or countably infinite, then X is a discrete random variable.Examples:∊∊Examples:X ∊{ 1, 2, 3, 4, 5 } (finite)X ∊{ 0, 2, 4, 6, ? } (countably infinite)Continuous Random Variables If the range of X is an interval (or collection of intervals) of real numbers, then X is a continuous random variable.Examples:∊∊∊Examples:X ∊[1.0, 10.0]X ∊(0.0, 1.0] or X ∊[-1.0, 0.0) ( is exclusive, [ is inclusiveInterval Probabilities: Continuous  for continuous random variables, probabilities must be computed over intervals:∫=<<badxxfbXaP)()(where f(x) is the probability density function (pdf).∫=<<adxxfbXaP)()(Interval Probabilities probability that r is in [a,b] is the area of shaded regionf(x)∫=<<badxxfbXaP )()(Interval Probabilitiesprobability0.11111 2 3 4 5 6 7 8 9 10arrival interval (minutes)%22.221111.0*21111.0)75(75===<<∫dxXPInterval Probabilities: Discrete for discrete random variables, probabilities summed over intervals:∑=≤≤bxfbXaP)()(where f(x) is the pdf∑==≤≤axxfbXaP)()(Uniform Distribution: Discreteprobability10%1 2 3 4 5 6 7 8 9 10arrival interval (minutes)%301.01.01.0)()75(75=++==≤≤∑=xxfXPCommon Distribution Functions Uniform Triangular ExponentialNormalNormalUniform Distributions Probability of any value is the same<≤=bxa,1<≤−=otherwisebxaabxf,0,1)(Triangular Distributions Probability peaks at some mode valuethen decreases to 0 at ends of range c is mode, a and b are rangeTriangular Distributionprobabilitya c bExponential Distributions Lambda is a rate (arrival rate, failure rate)Exponential Distributionsφ = 2φ= 1.5φ= 1.5φ = 1φ = 0.5Normal Distributions aka: Gaussian Distribution, Bell curve µ = mean (average)σ2= varianceNormal Distributions3σCumulative Distribution Functions A CDF defines the probability that a random variable is less than some given value. The CDF is the summation of a discrete PDFor integral of a continuous PDFCDF for Uniform DistributionPseudorandomness A pseudorandom process appears random, but isn’t Pseudorandom sequences exhibit statistical randomnessrandomness but generated by a deterministic process Pseudorandom sequences are easier to produce than a genuine random sequences Pseudorandom sequences can reproduce exactly the same numbers useful for testing and fixing software.Pseudorandom Generator Seeds Random number generators typically compute the next number in the sequence from the previous numberThe first number in a sequence The first number in a sequence is called the seed to get a new sequence, supply a new seed(current machine time is useful) to repeat a sequence, repeat the seedUniform Distribution Generation Most programming environments have some function for generating random numbers with a continuous uniform PDFC/C++: intrand() (cstdlib)C/C++:


View Full Document

PACIFIC COMP 155 - States and Events Random Numbers

Download States and Events Random Numbers
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view States and Events Random Numbers and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view States and Events Random Numbers 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?