Homework1：（(Important deadline: submit your homework on next Saturday, Oct. 17, 2009）
Questions ( from Data Networks) list:
3.6 A person enters a bank and finds all of the four clerks busy serving customers. There are no other customers in the bank, so the person will start service as soon as one of the customers in service leaves. Customers have independent, identical, exponential distribution of service time. (a) What is the probability that the person will be the last to leave the bank assuming that no other customers arrive?
(b) If the average service time is 1 minute, what is the average time the person will spend in the bank?
(c) Will the answer in part (a) change if there are some additional customers waiting in a common queue and customers begin service in the order of their arrival?
Solution：(a) 当该人开始接受服务时，其他3人的服务尚未结束，所有人剩下的服务时间仍为相同的指数分布。因此这个人最后离开的概率是1/4。
(b) 该人从进入银行到接受服务的时间等于min(X1,X2,X3,X4)，其中X1,X2,X3,X4为正在接受服务的4个客户的剩余服务时间。则
P[min(X1,X2,X3,X4)>x]=exp(-4μx)，为指数分布，均值=1/(4u)=0.25分钟。 所以该人在银行平均停留时间为1.25分钟。
(c) 不变。不管队列中有多少客户，当该人开始接受服务时，情况仍与(a)相同，所有人剩余服务时间仍为相同的指数分布。
3.8 Consider a packet stream whereby packets arrive according to a Poisson process with rate 10 packets/sec. If the interarrival time between any two packets is less than the transmission time of the first to arrive, the two packets are said to collide. (This notion will be made more meaningful in Chapter 4 when discuss multi-access schemes.) Find the probabilities that a packet does not collide with either its predecessor or it successor and that a packet does not collide with another packet, assuming:
(a) All packets have a transmission time of 20 msec. (Answer: both probabilities are equal to 0.67) (b) Packets have independent, exponentially distributed transmission time with mean 20 msec. (This part requires the M/M/∞ results.) (Answer: The probability of no collision with predecessor or successor is 0.694. The probability of no collision is 0.682)
Solution： (a) 设packet与前一个之间的到达间隔为τ1，与后一个之间的到达间隔为τ2，则与前后都不碰撞的概率
P=P[τ1>0.02]P[τ2>0.02]=e -2λ*0.02= e -2*10*0.02 和任何一个packet都不碰撞的概率与此相同。 (b) (1).P[no collision with predecessor or successor]=
P[τ2>s1] P[τ3>s2],其中, s1和s2分别为predecesor的传输时间和successor的传输时间.因为这些都是指数分布的独立的随机变量,所以,应用以下公式（习题3.12,或讲稿）,得到：
P[no collision with predecessor or successor]＝((μ/（λ+μ))^2 ,将λ＝10和μ＝1/0.02,代入上式得0.694. (2).P[no collision]＝P[zero customers in M/M/∞ and no arrival during his service]＝e-λ/μ P[τ>s],τ为下一到达间隔,s为服务时间.经计算可得该概率值为0.682. 上式的前一项即为队长是0的概率。
Questions from Kleinrock’s book (Queueing theory Vol.1):
2.1 Consider K independent sources of customers where the interarrival time between customers for each source is exponentially distributed with parameter ?k (i. e. each source is a Poisson
process). Now consider the arrival stream, which is formd by merging the input from each of the K sources defined above. Prove that this merged stream is also Poisson with parameter
???1??2????K.
Solution：证明见幻灯片，用归纳法证明。
2.2 Referring back to the previous problem, consider this merged Poisson stream and now assume that we wish to break it up into several branches. Let pi be the probability that a customer from the merged stream is assigned to the substream i. if the overall rate is λ customers per second, and if the sub stream probabilities pi are chosen for each customer indepencently, then show that each of these sub streams is a Poisson process with rate
?pi.
Solution：证明见幻灯片，用归纳法证明。
2.3 Let {Xj} be a sequence of identically distributed mutually independent Bernoulli random variables (with P[Xj=1]=p, and P[Xj=0]=1-p). Let SN=X1+…+XN be the sum of a random number N of the random variables Xj, where N has a Poisson distribution with mean ?. Prove that SN has a Poisson distribution with mean ?p . (In general, the distribution of the sum of a random number of independent random variables is called a compound distribution) Solution：
P?SN?m?e???kmmk?m??Ckp?1?p?k!k?0?e??pm?m!??k?m?!?1?p?k?0??kk?me??pm?m?m!?k!?1?p?k?0??kk
e??pm?m??1?p???em!me??p??p??m!因此SN服从均值为?p的Poisson分布。