Lecture 4: States and Events (pt 2) Random NumbersStates and EventsLast TimePetri NetsSlide 5Slide 6Slide 7Slide 8Slide 9Inputs to Petri NetsA Manufacturing LineManufacturing Line: Petri NetMutex - SemaphoreRandom Number GeneratorsProbabilistic ProcessesExample: Single Queue CheckoutSlide 17Probability DistributionsUniform DistributionsUniform Distribution: DiscreteUniform Distribution: ContinuousNon-uniform DistributionsDiscrete Random VariablesContinuous Random VariablesInterval Probabilities: ContinuousInterval ProbabilitiesInterval ProbabilitiesInterval Probabilities: DiscreteSlide 29Common Distribution FunctionsSlide 31Triangular DistributionsTriangular DistributionExponential DistributionsSlide 35Normal DistributionsSlide 37Cumulative Distribution FunctionsCDF for Uniform DistributionPseudorandomnessPseudorandom Generator SeedsUniform Distribution GenerationGenerating Random NumbersRejection MethodInverse MethodResources for RN GenerationSOURCESCOMP155Computer SimulationSeptember 8, 2008States and EventsA state is a condition of a system at some point in timeAn event is something that cause a system to shift from one state to anotherLast TimeFSA: Finite State Automataevent driven transitionsMarkov Modelsprobabalistic transitionsProduction Systemsrule based transitionsConditions and EventsPetri Netsplaces transitionstokensPetri NetsPlaces are conditionsTransitions are eventsTransitions can fire if all incoming places have a tokenFiring 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 NetsSome places can be designated as inputsMay be a time-based function for adding tokensMay be an infinite source of tokensA Manufacturing LineManufacturing Line: Petri NetMutex - Semaphoresemaphorecriticalsectioncriticalsectionhttp://www.cs.adelaide.edu.au/users/esser/mutual.htmlModeling UncertaintyProbabilistic ProcessesMany of the parameters in real-world systems are probabilistic rather than deterministicTo simulate these parameters, we need random number generatorsExample: Single Queue CheckoutConsider the following functional model for a single-queue of customers (i.e., a 7-11)Block 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.K QExample: Single Queue CheckoutSources of Randomness:Customer Arrival: time between customer arrivalsCheckout: time required to checkout 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 systemsreplicate the PD with appropriate random numbersProbability DistributionsA probability distribution describes the range of possible values that a random variable can attain, and the probability that the value of the random variable is within any subset of that rangeProbability distributions may be:continuous: allowing for all values in a range (real numbers)discrete: allowing for particular values in a range(integers)Uniform DistributionsA uniform distribution is one in which the probability of any of the possible values is the same.Example: The time between arrivals of customers is uniformly distributed over the range [1, 10] minutes.Uniform Distribution: Discrete10% 1 2 3 4 5 6 7 8 9 10arrival interval (minutes)probabilityIf we only allow for integer values in [1,10], then the probability of any one of those values is 10%.Sum of probabilities must be 1.0 (100%)Uniform Distribution: Continuous 1 2 3 4 5 6 7 8 9 10arrival interval (minutes)probabilityIf we allow for all real values in [1,10], we have a continuous probability distribution.Area under the curve must be 1.0 (100%)11.11%Non-uniform DistributionsNon-uniform distributions are described by functions, such as the familiar bell-shaped Gaussian distribution:likely values unlikely valuesDiscrete Random VariablesIf the number of possible values for X is finite or countably infinite, then X is a discrete random variable.Examples:X ∊ { 1, 2, 3, 4, 5 } (finite)X ∊ { 0, 2, 4, 6, … } (countably infinite)Continuous Random VariablesIf the range of X is an interval (or collection of intervals) of real numbers, then X is a continuous random variable.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:where f(x) is the probability density function (pdf).badxxfbXaP )()(Interval Probabilities probability that r is in [a,b] is the area of shaded regionf(x)badxxfbXaP )()(Interval Probabilities 1 2 3 4 5 6 7 8 9 10arrival interval (minutes)probability0.1111%22.221111.0*21111.0)75(75dxXPInterval Probabilities: Discretefor discrete random variables, probabilities summed over intervals:where f(x) is the pdfbaxxfbXaP )()(Uniform Distribution: Discreteprobability10% 1 2 3 4 5 6 7 8 9 10arrival interval (minutes)%301.01.01.0)()75(75xxfXPCommon Distribution FunctionsUniformTriangularExponentialNormalUniform DistributionsProbability of any value is the sameotherwisebxaabxf,0,1)(Triangular DistributionsProbability peaks at some mode valuethen decreases to 0 at ends of rangec is mode, a and b are rangeTriangular Distribution a c bprobabilityExponential DistributionsLambda is a rate (arrival rate, failure rate)Exponential Distributionsφ = 2φ = 1.5φ = 1φ = 0.5Normal Distributionsaka: Gaussian Distribution, Bell curveμ = mean (average)σ2 = varianceNormal Distributions3σCumulative Distribution FunctionsA 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 DistributionPseudorandomnessA pseudorandom process appears random, but isn’tPseudorandom sequences exhibit statistical randomness but generated by a deterministic processPseudorandom sequences are easier to produce than a genuine random sequencesPseudorandom sequences can
View Full Document