计算机网络数学基础：S.Keshav原著英文版

3星 · 超过75%的资源需积分: 10 43 浏览量更新于2024-07-18 收藏 2.66MB PDF 举报

"Mathematical Foundations of Computer Networking 是一本由Srinivasan Keshav撰写的英文原版书籍，主要探讨了计算机网络的数学基础。这本书是纪其进翻译的，适合研究生、研究人员和实践者阅读，他们需要对优化、信息论、博弈论、控制理论和排队论等计算机网络的理论基础有深入理解。书末还附有课后习题的答案，对于学习者来说是一份有价值的资源。" 正文：计算机网络的数学基础是构建和分析复杂网络系统的关键，而《Mathematical Foundations of Computer Networking》一书旨在填补这一领域的教育空白。传统的计算机科学本科课程往往不涵盖这些理论，使得自我学习或参加专门课程成为唯一选择，但这两种方式都存在挑战。作者Srinivasan Keshav通过这本书，为读者提供了一个集中的学习平台，仅需基础微积分知识，就能理解计算机网络的数学原理。本书涵盖了多个核心领域，首先是**优化理论**，在计算机网络中，优化问题无处不在，如路由算法的设计、带宽分配和资源调度等。书中可能介绍了线性规划、动态规划等方法，以及如何应用它们解决网络中的实际问题。其次，**信息论**是网络通信的基础，涉及数据编码、信道容量和编码效率等概念。读者将了解到香农定理、信噪比和信息熵等关键概念，并理解它们如何影响网络传输的效率和可靠性。接着，**博弈论**在多主体网络交互中起着重要作用，例如竞争资源的策略和合作模型。书中可能探讨了纳什均衡、合作博弈和非合作博弈等概念，以及它们在网络层协议设计和网络安全中的应用。 **控制理论**则关注网络系统的稳定性、反馈机制和控制策略。这包括状态空间模型、控制器设计和网络拥塞控制等内容，帮助读者理解如何维持网络性能的稳定。最后，**排队理论**用于分析网络中等待处理的数据包的分布和延迟，它是理解和改进网络性能的关键工具。书中可能会介绍M/M/1、M/D/1和G/G/1等排队模型，以及它们在网络流量建模和性能预测中的应用。这本书的独特之处在于它将这些理论与计算机网络的实际问题紧密结合，提供有针对性的案例和问题，使读者能更好地将所学应用于实际场景。此外，书后的习题答案为自主学习提供了便利，允许读者即时检验理解程度，巩固知识。《Mathematical Foundations of Computer Networking》是一本深入浅出的教材，适合那些希望强化计算机网络理论基础的读者。通过这本书，读者不仅可以掌握网络背后的数学原理，还能培养解决实际网络问题的能力。

DRAFT - Version 3 - Joint and conditional probability

To keep things simple, first consider the case when two events E and F share a common sample space and occur one after

the other. Suppose that the probability of E is and the probability of F is . Now, suppose that we are informed

that event E actually occurred. By definition, the conditional probability of the event F conditioned on the occurrence of

event E is denoted (read “the probability of F given E”) and computed as:

(EQ 4)

If knowing that E occurred does not affect the probability of F, E and F are said to be independent and

XAMPLE 11: CONDITIONAL PROBABILITY OF EVENTS DRAWN FROM THE SAME SAMPLE SPACE

Consider sample space and events and . Let and . Clearly,

the space . The joint event . Suppose . Then,

. We interpret this to mean that if event E occurred, then the probability that event

F occurs is 0.6. This is higher than the probability of F occurring on its own (which is 0.25). Hence, the fact the E occurred

improves the chances of F occurring, so the two events are not independent. This is also clear from the fact that



The notional of conditional probability generalizes to the case where events are defined on more than one sample space.

Consider a sequence of two processes with sample spaces and that occur one after the other (this could be the condi-

tion of the sky now, for instance, and whether or not it rains after two hours). Let event E be a subset of and let event F be

a subset of . Suppose that the probability of E is and the probability of F is . Now, suppose that we are

informed that event E actually occurred. We define the probability as the conditional probability of the event

F conditional on the occurrence of E as:

(EQ 5)

If knowing that E occurred does not affect the probability of F, E and F are said to be independent and

(EQ 6)

EXAMPLE 12: CONDITIONAL PROBABILITY OF EVENTS DRAWN FROM DIFFERENT SAMPLE SPACES

Consider sample space and sample space with product space

. Let be an event in and be an

event in . Also, let = 0.5 and let = 0.05.

If E and F are independent then:

E()

F()

SS×

FE()

SS×

FE()

SS×

EF∧()

E()

--------------------------------

SS×

EF()

E()

--------------------------==

SS×

EF()P

E()P

F()=

S 123,,{}=

E 1{}=

F 3{}=

E() 0.5=

F() 0.25=

SS× 11,()12,()…32,()33,(),,,,{}=

EF 13,(){}=

SS×

EF()0.3=

SS×

FE()

SS×

EF()

E()

--------------------------

0.3

0.5

------- 0 .6===

SS×

EF()0.3= P

E()P

F()≠ 0.125=

E()

F()

FE()

EF()

E()

-------------------------------=

EF() P

E() P

F()×=

123,,{}=

abc,,{}=

1 a,()1 b,()1 c,()2 a,()2 b,()2 c,()3 a,()3 b,()3 c,(),,,,,,,,{}

E 12,{}=

Fb{}=

E()

EF()P

1 b,()2 b,(),{}()=

EF()P

1 b,()2 b,(),{}()P

12,{}()P

b{}()×==

DRAFT - Version 3 -Conditional probability

Otherwise,



It is important not to confuse P(F|E) and P(F). The conditional probability is defined in the product space and the

unconditional probability in the space . Explicitly keeping track of the underlying sample space can help avoid apparent

contradictions such as the one discussed in Example 14.

XAMPLE 13: USING CONDITIONAL PROBABILITY

Consider a device that samples packets on a link, as in Example 8. Suppose that measurements show that 20% of the UDP

packets have a packet size of 52 bytes. Let P(UDP) denote the probability that the packet is of type UDP and let P(52)

denote the probability that the packet is of length 52 bytes. Then, P(52|UDP) = 0.2. In Example 8, we computed that

P(UDP) = 0.45. Therefore, P(UDP AND 52) = P(52|UDP) * P(UDP) = 0.2 * 0.45 = 0.09. That is, if we were to pick a

packet at random from the sample, there is a 9% chance that is a UDP packet of length 52 bytes (but it has a 20% chance of

being of length 52 bytes if we know already that it is a UDP packet).



XAMPLE 14: THE MONTY HALL PROBLEM

Consider a television show (loosely modelled on a similar show hosted by Monty Hall) where three identical doors hide two

goats and a luxury car. You, the contestant, can pick any door and obtain the prize behind it. Assume that you prefer the car

to the goat. If you did not have any further information, your chance of picking the winning door is clearly 1/3. Now, suppose

that after you pick one of the doors, say Door 1, the host opens one of the other doors, say Door 2, and reveals a goat behind

it. Should you switch your choice to Door 3 or stay with Door 1?

Solution:

We can view the Monty Hall problem as a sequence of three processes. The first process is the placement of a car behind one

of the doors. The second is the selection of a door by the contestant and the third process is the revelation of what lies behind

one of the other doors. The sample space for the first process is {Door 1, Door 2, Door 3} abbreviated {1, 2, 3}, as are the

sample spaces for the second and third processes. So, the product space is {(1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 2, 1),..., (3, 3, 3)}.

Without loss of generality, assume that you pick Door 1. The game show host’s hand is now forced: he has to pick either

Door 2 or Door 3. Without loss of generality, suppose that the host picks Door 2, so that the set of possible outcomes that

constitutes the reduced sample space is {(1, 1, 2), (2, 1, 2), (3, 1, 2)}. However, we know that the game show host will never

open a door with a car behind it - only a goat. Therefore, the outcome (2, 1, 2) is not possible. So, the reduced sample space

is just the set {(1, 1, 2), (3, 1, 2)}. What are the associated probabilities?

To determine this, note that the initial probability space is {1, 2, 3} with equiprobable outcomes. Therefore, the outcomes

{(1, 1, 2), (2, 1, 2), (3, 1, 2)} are also equiprobable. When the game show host makes his move to open Door 2, he reveals

private information that the outcome (2, 1, 2) is impossible, so the probability associated with this outcome is 0. The show

host’s forced move cannot affect the probability of the outcome (1, 1, 2) because the host never had the choice of opening

Door 1 once you selected it. Therefore, its probability in the reduced sample space continues to be 1/3. This means that

P({(3, 1, 2)} = 2/3, so it doubles your chances for you to switch doors.

0.05 0.5 P

b{}()×=

b{}()0.1=

FE()

EF()

E()

-------------------------------

0.05

0.5

---------- 0 .1===

DRAFT - Version 3 - Joint and conditional probability

One way to understand this somewhat counterintuitive result is to realize that the game show host’s actions reveal private

information, that is, the location of the car. Two-thirds of the time, the prize is behind the door you did not choose. The host

always opens a door that does not have a prize behind it. Therefore, the residual probability (2/3) must all be assigned to

Door 3. Another way to think of it is that if you repeat a large number of experiments with two contestants, one who never

switches doors and the other who always switches doors, then the latter would win twice as often.



1.2.3 Bayes’ rule

One of the most widely used rules in the theory of probability is due to an English country minister Thomas Bayes. Its signif-

icance is that it allows us to infer ‘backwards’ from effects to causes, rather than from causes to effects. The derivation of his

rule is straightforward, though its implications are profound.

We begin with the definition of conditional probability (Equation 4):

If the underlying sample spaces can be assumed to be implicitly known, we can rewrite this as:

(EQ 7)

We interpret this to mean that the probability that both E and F occur is the product of the probabilities of two events, first,

that E occurs, and second, that conditional on E, F occurs.

Recall that P(F|E) is defined in terms of the event F following event E. Now, consider the converse: F is known to have

occurred–what is the probability that E occurred? This is similar to the problem: if there is fire, there is smoke, but if we see

smoke, what is the probability that it was due to a fire? The probability we want is P(E|F). Using the definition of conditional

probability it is given by:

(EQ 8)

Substituting for P(F) from Equation 7, we get

(EQ 9)

which is Bayes’ rule. One way of interpreting this is that it allows us to compute the degree to which some effect or poste-

rior F can be attributed to some cause or prior E.

XAMPLE 15: BAYES’ RULE

Continuing with Example 13, we want to compute the following quantity: Given that a packet is 52 bytes long, what is the

probability that it is a UDP packet?

Solution:

From Bayes’ rule:



SS×

FE()

SS×

EF()

E()

--------------------------=

PEF() PFE()PE()=

PEF()

PF()

----------------=

PEF()

PFE()

PF()

------------------

PE()=

PUDP52()

P 52 UDP()P UDP()

P 52()

----------------------------------------------------

0.2 0.45()

0.54

----------------------- 0.167===

DRAFT - Version 3 -Bayes’ rule

We can generalize Bayes’ rule when a posterior can be attributed to more than one prior. Consider a posterior F that is due to

some set of n priors E

such that the priors are mutually exclusive and exhaustive (that is, at least one of them occurs and only

one of them can occur). This implies that . Then,

(EQ 10)

This is also called the Law of Total Probability.

XAMPLE 16: LAW OF TOTAL PROBABILITY

Continuing with Example 13, let us compute P(52), that is, the probability that a packet sampled at random has a length of 52

bytes. To compute this, we need to know the packet sizes for all other traffic types. For instance, if P(52| TCP) = 0.9 and all

other packets were known to be of length other than 52 bytes, then P(52) = P(52|UDP) * P(UDP) + P(52|TCP) * P(TCP) +

P(52|other) * P(other) = 0.2 * 0.45 + 0.9 * 0.5 + 0 = 0.54.



The law of total probability allows one further generalization of Bayes’ rule to obtain Bayes’ Theorem. From the definition

of conditional probability, we have:

From Equation 7,

Substituting Equation 10, we get

(EQ 11)

This is called the generalized Bayes’ rule or Bayes’ Theorem. It allows us to compute the probability of any one of the pri-

ors E

, conditional on the occurrence of the posterior F. This is often interpreted as follows: we have some set of mutually

exclusive and exhaustive hypotheses E

. We conduct an experiment, whose outcome is F. We can then use Bayes’ formula to

compute the revised estimate for each hypothesis.

XAMPLE 17: BAYES’ THEOREM

Continuing with Example 15, consider the following situation: we pick a packet at random from the set of sampled packets

and find that its length is not 52 bytes. What is the probability that it is a UDP packet?

Solution:

As in Example 6, let ‘UDP’ refer to the event that a packet is of type UDP and ‘52’ refer to the event that the packet is of

length 52 bytes. Denote the complement of the latter event, that is, that the packet is not of length 52 bytes by ‘52

’.

()

i 1=

∑

PF() PFE

()

i 1=

∑

PFE

()PE

()

i 1=

∑

F()

PF()

------------------=

F()

PFE

()PE

()

PF()

----------------------------------=

F()

PFE

()PE

()

PFE

()PE

()

i 1=

∑

⎝⎠

⎜⎟

⎛⎞

--------------------------------------------------=

DRAFT - Version 3 - Random variables

From Bayes’ rule:

Thus, if we see a packet that is not 52 bytes long, it is quite likely that it is a UDP packet. Intuitively, this must be true

because most TCP packets are 52 bytes long, and there aren’t very many non-UDP and non-TCP packets.



1.3 Random variables

So far, we have restricted our consideration to studying events, which are collections of outcomes of experiments or observa-

tions. However, we are often interested in abstract quantities or outcomes of experiments that are derived from events and

observations, but are not themselves events or observations. For example, if we throw a fair die, we may want to compute the

probability that the square of the face value is smaller than 10. This is random and can be associated with a probability, and,

moreover, depends on some underlying random events. Yet, it is neither an event nor an observation: it is a random varia-

ble. Intuitively, a random variable is a quantity that can assume any one of a set of values (called its domain D) and whose

value can only be stated probabilistically. In this section, we will study random variables and their distributions.

More formally, a real random variable (the one most commonly encountered in applications having to do with computer

networking) is a mapping from events in a sample space S to the domain of real numbers. The probability associated with

each value assumed by a real random variable

is the probability of the underlying event in the sample space as illustrated in

Figure 1.

Figure 1. The random variable X takes on values from the domain D. Each value taken on by the random variable

is associated with a probability corresponding to an event E, which is a subset of outcomes in the sample space S.

A random variable is discrete if the set of values it can assume is finite and countable. The elements of D should be mutually

exclusive (that is, the random variable cannot simultaneously take on more than one value) and exhaustive (the random vari-

able cannot assume a value that is not an element of D).

XAMPLE 18: A DISCRETE RANDOM VARIABLE

2. We deal with only real random variables in this text so will drop the qualifier ‘real’ at this point.

PUDP52

()

P 52

UDP()P UDP()

P 52

UDP()P UDP()P 52

TCP()PTCP()P 52

other()Pother()++

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------=

0.8 0.45()

0.8 0.45()0.1 0.5()10.05()++

--------------------------------------------------------------------------=

0.78=

{}

...

outcome

event

{}

X ⊂ D

...

剩余323页未读，继续阅读

Mikchy

粉丝: 279
资源: 4

计算机网络数学基础：S.Keshav原著英文版

computer networking 中文版1-9

Foundations of Modern Cryptograph

计算机网络数学基础

Mathematical Foundations of Computer

HANDBOOK OF MATHEMATICAL MODELS IN COMPUTER VISION英文原版文字版

Mathematical Foundations of Data Sciences

Mathematical Foundations Of Quantum Mechanics

Mathematical Foundations of Computing.pdf

计算机网络数学基础--Mathematical.Foundations.of.Computer.Networking

The mathematical foundations of learning machines-Morgan Kaufmann (2005)

最新资源