### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Computer Networks CSC 570

NCS

GPA 3.94

### View Full Document

## 5

## 0

## Popular in Course

## Popular in ComputerScienence

This 18 page Class Notes was uploaded by Jaden Jakubowski on Thursday October 15, 2015. The Class Notes belongs to CSC 570 at North Carolina State University taught by Rudra Dutta in Fall. Since its upload, it has received 5 views. For similar materials see /class/223819/csc-570-north-carolina-state-university in ComputerScienence at North Carolina State University.

## Popular in ComputerScienence

## Reviews for Computer Networks

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/15/15

Notes on Renewal Counting Rudra Dutta Renewal Processes Let X 139 2 1 be a set ofz39z39al integer valued RV s We think ole for successive values ofz39 as durations running sequentially one after another It is convenient to think of the successive time periods to be lifetimes of components which need replacements or need to be renewed at random times For example we may have a electric lamp which needs a light bulb At any time we do not need any more than one light bulb When one burns out we replace it with a very similar light bulb The lifetime of a light bulb of the type we use varies according to some probability distribution and we denote the successive lifetimes by the variables X We define the partial sums Sn 2H X for n 2 l The value of Squot is called the time of the nth renewal epoch We further define Nm to be the number of renewal epochs found in the first m time units m 2 0 Nm is obviously a RV and is called the renewal counting process for X Thus the distribution ofNm is given by PNm S n PSn1 gt m Example Geometric Random Variables Let X be geometrically distributed with parameter p Consider another way to view the time axis We consider each renewal epoch as a marked time unit whereas other time units which do not terminate in an epoch are considered unmarked The same result would be obtained by considering each time unit 1 2 3 in sequence and marking each independently with probability p When considered this way it becomes clear that PNm n probability of n markings out of m and is given by the Binomial probability Cmy n pquot1 pm39quot Thus the renewal process for geometrically distributed variables is binomially distributed This result can also be obtained more rigorously Continuous Analogues When an integer variable G is distributed geometrically there is a probability p of the duration specified by G ending at any given time unit n but G cannot terminate at fractional values of n Consider a continuous analogue of G which has equal probability of terminating at any instant tof time However now this probability cannot be a nonzero quantity such as p because there would no longer be any bound on the probability over a finite period of time To understand the transition to continuous variables consider a geometric variable for which time is sliced thinner and thinner while the probability of terminating at any given time slice becomes less and less so that the probability of the variable terminating over a finitely large period of time such as our original time unit remains the same In the limit the distribution obtained is exponential as can be verified rigorously Similarly it can be shown that the Poisson distribution is the limiting case of a binomial distribution Intuitively the binomial is the result of the sum of n Bernoulli variables each of which has a success probability of kn whereas the Poisson variable is the sum of an in nite number of Bernoulli variables each of which has in nitesimal success probability keeping the product 7 constant Combining this with our discussion on renewal counting it is now obvious that the renewal process of exponentially distributed variables is a Poisson process This too can be established rigorously from the de nitions of the two distributions Properties A few of the properties of the exponential and Poisson distributions that can be understood in terms of the renewal paradigm are listed below without reasoning If requests such as packets arrive for service such as transmission such that the number of requests over time follows a Poisson distribution then the request interarrival time is distributed exponentially with the same parameter 7 If request interarrival times are exponential then the number of requests over time follows a Poisson distribution with the same parameter 7 If two or more independent Poisson processes are merged into a single process the resultant process is also Poisson and its rate is the sum of the rates of the constituent processes If a Poisson process is statistically split into two processes using a Bernoulli variable for the splitting then the resultant processes are each Poisson Probability Theory Refresher Notes Dr Arne Nilsson Dr Atef Zaghloul Probability ProbabilitV and Random Variables I A Random Variable X is a variable whose value depends upon the outcome of a random experiment Since the outcomes of our random experiments are represented as points a e S then to each such outcome 0 we associate a real number Xa which is in fact the value the random variables takes on when the experiment outcome is a PXXi Pi And 0 SE S 1 for all i n 2 And i1 Pi 1 Example of a Roulette wheel Say N number of slots 6 N slots marked with n s N different numbers X1 9 X2 X3 q X1 1 N1 2 X2 2 N2 1 X3 3 N3 1 X4 4 N4 2 N6Il4 PiNiN Probability that 1 appears gt P1 2 6 13 Probability that 2 appears gt P2 1 6 Probability that 3 appears gt P3 1 6 Probability that 4 appears gt P4 2 6 13 PP1P2P3P4131616131 Say we have A set of values that x can take 213 Px e A XI The probability that x takes a value in A is de ned as the sum of the probabilities Pi of all the values Xi in A Example A 13 q Pxe A P1P3 b P12613 and P316 A roulette wheel has only nite number of outcomes Px e A 16 13 12 We will now consider a case with in nite number of outcomes Example of in nite number of outcomes 9 Count the number of photons Y that hit a photo detector in a time interval of 1 minute 9 Repeat the experiment many number of times 9 The fraction of experiments when Y n is a a P n n20 amp 06 isareNumber 00 am a Note 6 Z 39 mzo m Therefore 0 3 P11 S 1 for all 11 And ZP1 As before we de ne 2P PYe A l leA A Random Variable with the probability above is called a Poisson Random Variable with parameter 05 So far our random variables admitted values in a countable set ie we could enumerate the possible values as x1 x2 x3 The random variables that we examine next takes arbitrary values in 0 00 Say the lifetime of a communication link 2I Pxgtt e where t 20amp A isareNo Px s t 1Pxgtt 4 1 6 The above random variable is said to be exponentially distributed with rate A PXe tt8PX gtt PX gttg 6 21 e ll8 e tl 6 31 6 18 e ll 6 18 18 for very small 8 and using 6 z 1 18 fort E CmeSlSI ft is called the Probability Density Function pdf of the random variable x Thus the pdf of an exponentially distributed random variable with rate 1 is flleh for t 2 0 0 for tlt O Conditional Probability We de ne PAB gt Conditional probability of A given B De nition PAB PA and BPB Roulette wheel Example A 1 B123 b PxEAxE B N1N1N2N3 Divide both numerator amp denominator by N N1NN1N2N3N PXE X1PXE x1 x2 x3 Example 2 Let Y be a poisson random variable with parameter 1 Then PY1 Y gt0 PY1 amp Ygt0PY20 26 1 PY11PY0 1 e1 Example 3 Let x be the exponential lifetime of a light bulb We want to estimate the probability that a light bulb that has been on for a seconds will survive for at least t more seconds We want to calculate Pxgtxt xgta Pxgtat xgta PxgtatPxgta will e W Px gt t e Expectation The expected value also called the average or mean value of a random variable is the arithmetic mean of the values observed when the random experiment is replicated many times Let X be a random variable Then the expected value EX of X is de ned as the sum of values of X weighted by their probabilities 21xiPX xi Example A random variable X is geometrically distributed with parameter p 6 01 PXn 1 pp 391 for n 123 EX 21nPX n EX Zlnlt1 pgtpquot l Example 2 Consider a Poisson random variable X with parameter 2 fxx1 w for x 2 O 0 for x lt O x EX jx e lxdx put 2x u 0 Variance of X VX EX2 EX2 For the above example VX 1 12 Independence Two random variables are independent if knowing the value of one does not provide information about the value of the other Two random variables XampY are said to be independent when PXxi and Y yj PXxi PY yj 1 From this relation we can conclude EXYE XEY 2 However the opposite is not true ie if equation 2 holds this does not mean that any 2 random variables are independent Regenerative Method Assumptions 0 A packet is correctly transmitted with a probability 1p o A packet in error must be retransmitted 0 Transmission of packets is independent 0 X number of transmissions needed to get a correct packet PXn1p 3911p X 1 with probab 1p 1Y with probab P where XampY are equal in distribution since transmissions are independent So EX139P1 P1EY note EXEY EX1pppEX 1300 11P Example 3 days gt 1 day C 5 days Prison cell I I I I Free Assume o It takes 1 day to get to any door 0 Inmate forgets which door he takes every time X number of days for freedom How many days for freedom 3 days gt 1daylt Prison cell Sdays X 1 2Y1 4Y2 6Y3 where X Y1Y2Y3 are equal in distribution Therefore EXEY1EY2EY3 I I I I Free prob 14 prob 14 prob 14 prob 14 So 1A12EY14EY26EY3 EX 133EX EX 13

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.