《【精品PPT】probability(1p).ppt》由会员分享，可在线阅读，更多相关《【精品PPT】probability(1p).ppt（51页珍藏版）》请在三一办公上搜索。
1、1,Chapter 2,Probability,Statistics,and Traffic Theories,Copyright 2002,Dr.Dharma P.Agrawal and Dr.Qing-An Zeng.All rights reserved,2,Outline,IntroductionProbability Theory and Statistics TheoryRandom variablesProbability mass function(pmf)Probability density function(pdf)Cumulative distribution func
2、tion(cdf)Expected value,nth moment,nth central moment,and varianceSome important distributionsTraffic TheoryPoisson arrival model,etc.Basic Queuing SystemsLittles lawBasic queuing models,3,Introduction,Several factors influence the performance of wireless systems:Density of mobile usersCell sizeMovi
3、ng direction and speed of users(Mobility models)Call rate,call durationInterference,etc.Probability,statistics theory and traffic patterns,help make these factors tractable,4,Probability Theory and Statistics Theory,Random Variables(RVs)Let S be sample associated with experiment EX is a function tha
4、t associates a real number to each s SRVs can be of two types:Discrete or ContinuousDiscrete random variable=probability mass function(pmf)Continuous random variable=probability density function(pdf),5,Discrete Random Variables,In this case,X(s)contains a finite or infinite number of valuesThe possi
5、ble values of X can be enumeratedE.g.,throw a 6 sided dice and calculate the probability of a particular number appearing.,1,2,3,4,6,0.1,0.3,0.1,0.1,0.2,0.2,5,Probability,Number,6,Discrete Random Variables,The probability mass function(pmf)p(k)of X is defined as:p(k)=p(X=k),for k=0,1,2,.where1.Proba
6、bility of each state occurring 0 p(k)1,for every k;2.Sum of all states p(k)=1,for all k.,7,Continuous Random Variables,In this case,X contains an infinite number of valuesMathematically,X is a continuous random variable if there is a function f,called probability density function(pdf)of X that satis
7、fies the following criteria:1.f(x)0,for all x;2.f(x)dx=1.,8,Cumulative Distribution Function,Applies to all random variablesA cumulative distribution function(cdf)is defined as:For discrete random variables:For continuous random variables:,9,Probability Density Function,The pdf f(x)of a continuous r
8、andom variable X is the derivative of the cdf F(x),i.e.,10,Discrete Random VariablesExpected value represented by E or average of random variablenth momentnth central momentVariance or the second central moment,Expected Value,nth Moment,nth Central Moment,and Variance,2=Var(X)=E(X EX)2=EX2-(EX)2,11,
9、Expected Value,nth Moment,nth Central Moment,and Variance,1,2,3,4,5,6,0.1,0.3,0.1,0.1,0.2,0.2,EX=0.166,12,Continuous Random VariableExpected value or mean valuenth momentnth central momentVariance or the second central moment,Expected Value,nth Moment,nth Central Moment,and Variance,2=Var(X)=E(X EX)
10、2=EX2-(EX)2,13,Some Important Discrete Random Distributions,Poisson EX=,and Var(X)=GeometricEX=1/(1-p),and Var(X)=p/(1-p)2,P(X=k)=p(1-p)k-1,where p is success probability,14,Some Important Discrete Random Distributions,Binomial Out of n dice,exactly k dice have the same value:probability p k and(n-k
11、)dice have different values:probability(1-p)n-k.For any k dice out of n:,15,Some Important Continuous Random Distributions,NormalEX=,and Var(X)=2,16,Some Important Continuous Random Distributions,UniformEX=(a+b)/2,and Var(X)=(b-a)2/12,17,Some Important Continuous Random Distributions,ExponentialEX=1
12、/,and Var(X)=1/2,18,Multiple Random Variables,There are cases where the result of one experiment determines the values of several random variablesThe joint probabilities of these variables are:Discrete variables:p(x1,xn)=P(X1=x1,Xn=xn)Continuous variables:cdf:Fx1x2xn(x1,xn)=P(X1 x1,Xn xn)pdf:,19,Ind
13、ependence and Conditional Probability,Independence:The random variables are said to be independent of each other when the occurrence of one does not affect the other.The pmf for discrete random variables in such a case is given by:p(x1,x2,xn)=P(X1=x1)P(X2=x2)P(X3=x3)and for continuous random variabl
14、es as:FX1,X2,Xn=FX1(x1)FX2(x2)FXn(xn)Conditional probability:is the probability that X1=x1 given that X2=x2.Then for discrete random variables the probability becomes:and for continuous random variables it is:,20,Bayes Theorem,A theorem concerning conditional probabilities of the form P(X|Y)(read:th
15、e probability of X,given Y)is where P(X)and P(Y)are the unconditional probabilities of X and Y respectively.,21,Important Properties of Random Variables,Sum property of the expected value Expected value of the sum of random variables:Product property of the expected valueExpected value of product of
16、 stochastically independent random variables,22,Important Properties of Random Variables,Sum property of the variance Variance of the sum of random variables iswhere covXi,Xj is the covariance of random variables Xi and Xj andIf random variables are independent of each other,i.e.,covXi,Xj=0,then,23,
17、Important Properties of Random Variables,Distribution of sum-For continuous random variables with joint pdf fXY(x,y)and if Z=(X,Y),the distribution of Z may be written as where Z is a subset of Z.For a special case Z=X+YIf X and Y are independent variables,the fXY(x,y)=fX(x)fY(y)If both X and Y are
18、non negative random variables,then pdf is the convolution of the individual pdfs,fX(x)and fY(y).,24,Central Limit Theorem,The Central Limit Theorem states that whenever a random sample(X1,X2,.Xn)of size n is taken from any distribution with expected value EXi=and variance Var(Xi)=2,where i=1,2,.,n,t
19、hen their arithmetic mean is defined by,25,Central Limit Theorem,The sample mean is approximated to a normal distribution with ESn=,and Var(Sn)=2/n.The larger the value of the sample size n,the better the approximation to the normal.This is very useful when inference between signals needs to be cons
20、idered.,26,Poisson Arrival Model,A Poisson process is a sequence of events“randomly spaced in time”.For example,customers arriving at a bank and Geiger counter clicks are similar to packets arriving at a buffer.The rate of a Poisson process is the average number of events per unit time(over a long t
21、ime).,27,Properties of a Poisson Process,Properties of a Poisson processFor a time interval 0,t,the probability of n arrivals in t units of time isFor two disjoint(non overlapping)intervals(t1,t2)and(t3,t4),(i.e.,t1 t2 t3 t4),the number of arrivals in(t1,t2)is independent of arrivals in(t3,t4),28,In
22、terarrival Times of Poisson Process,Interarrival times of a Poisson processWe pick an arbitrary starting point t0 in time.Let T1 be the time until the next arrival.We have P(T1 t)=P0(t)=e-tThus the cumulative distribution function of T1 is given by FT1(t)=P(T1 t)=1 e-tThe pdf of T1 is given by fT1(t
23、)=e-tTherefore,T1 has an exponential distribution with mean rate.,29,Exponential Distribution,Similarly T2 is the time between first and second arrivals,we define T3 as the time between the second and third arrivals,T4 as the time between the third and fourth arrivals and so on.The random variables
24、T1,T2,T3 are called the interarrival times of the Poisson process.T1,T2,T3,are independent of each other and each has the same exponential distribution with mean arrival rate.,30,Memoryless and Merging Properties,Memoryless propertyA random variable X has the property that“the future is independent
25、of the past”i.e.,the fact that it hasnt happened yet,tells us nothing about how much longer it will take before it does happen.Merging propertyIf we merge n Poisson processes with distributions for the inter arrival times 1-e-it where i=1,2,ninto one single process,then the result is a Poisson proce
26、ss for which the inter arrival times have the distribution 1-e-t with mean=1+2+.+n.,31,Basic Queuing Systems,What is queuing theory?Queuing theory is the study of queues(sometimes called waiting lines).Can be used to describe real world queues,or more abstract queues,found in many branches of comput
27、er science,such as operating systems.Basic queuing theoryQueuing theory is divided into 3 main sections:Traffic flowSchedulingFacility design and employee allocation,32,Kendalls Notation,D.G.Kendall in 1951 proposed a standard notation for classifying queuing systems into different types.Accordingly
28、 the systems were described by the notation A/B/C/D/E where:,33,Kendalls notation,A and B can take any of the following distributions types:,34,Littles Law,Assuming a queuing environment to be operating in a stable steady state where all initial transients have vanished,the key parameters characteri
29、zing the system are:the mean steady state consumer arrivalN the average no.of customers in the systemT the mean time spent by each customer in the systemwhich gives N=T,35,Markov Process,A Markov process is one in which the next state of the process depends only on the present state,irrespective of
30、any previous states taken by the process.The knowledge of the current state and the transition probabilities from this state allows us to predict the next state.,36,Birth-Death Process,Special type of Markov process Often used to model a population(or,no.of jobs in a queue).If,at some time,the popul
31、ation has n entities(n jobs in a queue),then birth of another entity(arrival of another job)causes the state to change to n+1.On the other hand,a death(a job removed from the the queue for service)would cause the state to change to n-1.Any state transitions can be made only to one of the two neighbo
32、ring states.,37,The state transition diagram of the continuous birth-death process,State Transition Diagram,0,1,2,n-1,n,n+1,0,1,1,2,2,3,n-2,n-1,n-1,n,n,n+1,n+1,n+2,38,M/M/1/or M/M/1 Queuing System,When a customer arrives in this system it will be served if the server is free.Otherwise the customer i
33、s queued.In this system customers arrive according to a Poisson distribution and compete for the service in a FIFO(first in first out)manner.Service times are independent identically distributed(IID)random variables,the common distribution being exponential.,39,Queuing Model and State Transition Dia
34、gram,The M/M/1/queuing model,The state transition diagram of the M/M/1/queuing system,40,Equilibrium State Equations,If mean arrival rate is and mean service rate is,i=0,1,2.be the number of customers in the system and P(i)be the state probability of the system having i customers.From the state tran
35、sition diagram,the equilibrium state equations are given by,41,Traffic Intensity,We know that the P(0)is the probability of server being free.Since P(0)0,the necessary condition for a system being in steady state is,This means that the arrival rate cannot be more than the service rate,otherwise an i
36、nfinite queue will form and jobs will experience infinite service time.,42,Queuing System Metrics,=1 P(0),is the probability of the server being busy.Therefore,we have P(i)=i(1-)The average number of customers in the system isLs=The average dwell time of customers is Ws=,43,Queuing System Metrics,Th
37、e average queuing length is,The average waiting time of customers is,44,M/M/S/Queuing Model,45,State Transition Diagram,46,Queuing System Metrics,The average number of customers in the system is,The average dwell time of a customer in the system is given by,47,Queuing System Metrics,The average queu
38、e length is,The average waiting time of customers is,48,M/G/1/Queuing Model,We consider a single server queuing system whose arrival process is Poisson with mean arrival rate.Service times are independent and identically distributed with distribution function FB and pdf fb.Jobs are scheduled for ser
39、vice as FIFO.,49,Basic Queuing Model,Let N(t)denote the number of jobs in the system(those in queue plus in service)at time t.Let tn(n=1,2,.)be the time of departure of the nth job and Xn be the number of jobs in the system at time tn,so thatXn=N(tn),for n=1,2,.The stochastic process can be modeled
40、as a discrete Markov chain known as imbedded Markov chain,which helps convert a non-Markovian problem into a Markovian one.,50,Queuing System Metrics,The average number of jobs in the system,in the steady state is The average dwell time of customers in the system isThe average waiting time of customers in the queue isAverage waiting time of customers in the queue isThe average queue length is,51,
