Gallager《随机过程理论应用》习题精选解答

版权申诉

随机过程

Gallager

5星 · 超过95%的资源 18 浏览量更新于2024-07-21 收藏 2.33MB PDF 举报

身份认证购VIP最低享 7 折!

30元优惠券

资源详情

资源推荐

16 APPENDIX A. SOLUTIONS TO EXERCISES

where a(n) ⇠ b(n) means that lim

n!1

a(n)/b(n) = 1.

Solution: Note that (A.6) provides an upper bound to



k+`



and a slight modiﬁcation of

the same argument provides the lower bound



k+`









nk`

k+`



. Taking the ratio of the

upper to lower bound for ﬁxed ` and ˜p as n ! 1, we see that

✓

k + `

◆

⇠

✓

◆

n  k



so that

(k + `) ⇠ p

(k)(˜qp/˜pq)

(A.9)

follows. Replacing the upper bound in (A.8) with the asymptotic equality in (A.9), and

letting ` grow very slowly with n, we get Pr{S

 k} ⇠

˜pq

˜pp

(k).

Exercise 1.39: Let {X

; i  1} be IID binary rv’s. Let Pr{X

= 1} = , Pr{X

= 0} = 1  . Let

= X

+ ··· + X

. Let m be an arbitrary but ﬁxed positive integer. Think! then evaluate the following

and explain your answers:

a) lim

n!1



i: nmin+m

Pr{S

= i}.

Solution: It is easier to reason about the problem if we restate the sum in the following

way:

i: nmin+m

Pr{S

= i} = Pr{n  m  S

 n + m}

= Pr



m  S

 nX  m

= Pr

⇢

m





 nX









where  is the standard deviation of X. Now in the limit n ! 1, (S

 nX)/

approaches a normalized Gaussian rv in distribution, i.e.,

lim

n!1

⇢

m





 nX









= lim

n!1

⇥









 



m



⇤

= 0.

This can also be seen immediately from the binomial distribution as it approaches a discrete

Gaussian distribution. We are looking only at essentially the central 2m terms of the

binomial, and each of those terms goes to 0 as 1/

n with increasing n.

b) lim

n!1



i :0in+m

Pr{S

= i}.

Solution: Here all terms on lower side of the distribution are included and the upper side

is bounded as in (a). Arguing in the same way as in (a), we see that

i:0in+m

Pr{S

= i} = Pr

⇢

 nX









In the limit, this is (0) = 1/2.

c) lim

n!1



i :n(1/m)in(+1/m)

Pr{S

= i}.

A.1. SOLUTIONS FOR CHAPTER 1 17

Solution: Here the number of terms included in the sum is increasing linearly with n, and

the appropriate mechanism is the WLLN.

i:n(1/m)in(+1/m)

{

= i

}

= Pr

⇢





 nX





In the limit n ! 1, this is 1 by the WLLN. The essence of this exercise has been to scale

the random variables properly to go the limit. We have used the CLT and the WLLN, but

one could guess the answers immediately by recognizing what part of the distribution is

being looked at.

Exercise 1.44: Let X

, X

. . . be a sequence of IID rv’s each with mean 0 and variance 

. Let

= X

+ ··· + X

for all n and consider the random variable S

/

n  S

/

2n. Find the limiting

CDF for this sequence of rv’s as n ! 1. The point of this exercise is to see clearly that the CDF of

/

n  S

/

2n is converging in n but that the sequence of rv’s is not converging in any reasonable

sense.

Solution: If we write out the above expression in terms of the X

, we get







i=1













i=n+1



The ﬁrst sum above approaches a Gaussian distribution of variance (1  1/

and the

second sum approaches a Gaussian distribution of variance 1/2. Since these two terms are

independent, the di↵erence approaches a Gaussian distribution of variance 1 + (1 1/

This means that the distribution of the di↵erence does converge to this Gaussian rv as

n ! 1. As n increases, however, this di↵erence slowly changes, and each time n is doubled,

the new di↵erence is only weakly correlated with the old di↵erence.

Note that S

/n

behaves in this same way. The CDF converges as n ! 1, but the rv’s

themselves do not approach each other in any reasonable way. The point of the problem

was to emphasize this property.

Exercise 1.47: Consider a discrete rv X with the PMF

(1) = (1  10

10

)/2,

(1) = (1  10

10

)/2,

(10

) = 10

10

a) Find the mean and variance of X. Assuming that {X

; m  1} is an IID sequence with the distribution

of X and that S

= X

+ ···+ X

for each n, ﬁnd the mean and variance of S

. (no explanations needed.)

Solution: X = 100 and 

= 10

+ (1  10

10

)  10

⇡ 10

. Thus S

= 100n and



⇡ n ⇥ 10

b) Let n = 10

and describe the event {S

 10

} in words. Find an exact expression for Pr



 10



(10

Solution: This is the event that all 10

trials result in ±1. That is, there are no occurrences

of 10

. Thus Pr



 10

= (1  10

10

)

18 APPENDIX A. SOLUTIONS TO EXERCISES

c) Find a way to use the union bound to get a simple upper bound and approximation of 1  F

(10

Solution: From the union bound, the probability of one or more occurrences of the sample

value 10

out of 10

trials is bounded by a sum of 10

terms, each equal to 10

10

, i.e.,

1  F

(10

)  10

4

. This is also a good approximation, since we can write

(1  10

10

)

= exp

⇣

ln(1  10

10

)

⌘

⇡ exp(10

· 10

10

) ⇡ 1  10

4

d) Sketch the CDF of S

for n = 10

. You can choose the horizontal axis for your sketch to go from 1

to +1 or from 3 ⇥ 10

to 3 ⇥ 10

or from 10

to 10

or from 0 to 10

, whichever you think will best

describe this CDF.

Solution: Conditional on no occurrences of 10

, S

simply has a binomial distribution.

We know from the central limit theorem for the binomial case that S

will be approxi-

mately Gaussian with mean 0 and standard deviation 10

. Since one or more occurrences

of 10

occur only with probability 10

4

, this can be neglected in the sketch, so the CDF is

approximately Gaussian with 3 sigma points at ±3 ⇥ 10

. There is a little blip, in the 4th

decimal place out at 10

which doesn’t show up well in the sketch, but of course could be

important for some purp oses such as calculating 

3 ⇥ 10

e) Now let n = 10

. Give an exact expression for Pr



 10



and show that this can be approximated

by e

1

. Sketch the CDF of S

for n = 10

, using a horizontal axis going from slightly below 0 to slightly

more than 2 ⇥ 10

. Hint: First view S

as conditioned on an appropriate rv.

Solution: First consider the PMF p

(j) of the numb er B = j of occurrences of the value

. We have

(j) =

✓

◆

(1  p)

j

where p = 10

10

(0) = (1  p)

= exp{10

ln[1  p]} ⇡ exp(10

p) = e

1

(1) = 10

p(1  p)

1

= (1  p)

1

⇡ e

1

(2) =

✓

◆

(1  p)

2

⇡

1

Conditional on B = j, S

will be approximately Gaussian with mean 10

j and standard

deviation 10

. Thus F

(s) rises from 0 to e

1

over a range from about 3⇥10

to +3⇥10

It then stays virtually constant up to about 10

3 ⇥10

. It rises to 2/e by 10

+ 3 ⇥10

20 APPENDIX A. SOLUTIONS TO EXERCISES

A.2 Solutions for Chapter 2

Exercise 2.1: a) Find the Erlang density f

(t) by convolving f

(x) =  exp(x), x  0 with itself n

times.

Solution: For n = 2, we convolve f

(x) with itself.

(t) =

(x)f

(t  x) dx =

e

x

e

(tx)

dx = 

t

For larger n, convolving f

(x) with itself n times is found by taking the convolution n1

times, i.e., f

n1

(t), and convolving this with f

(x). Starting with n = 3,

(t) =

(x)f

(t  x) dx =



x

e

(tx)

dx =



t

(t) =



x

· e

(tx)

dx =



t

We now see the pattern; each additional integration increases the power of  and t by 1

and multiplies the denominator by n  1. Thus we hypothesize that f

(t) =



n1

t

If one merely wants to verify the well-known Erlang density, one can simply use induction

from the beginning, but it is more satisfying, and not that much more diﬃcult, to actually

derive the Erlang density, as done above.

b) Find the moment generating function of X (or ﬁnd the Laplace transform of f

(x)), and use this to ﬁnd

the moment generating function (or Laplace transform) of S

= X

+ X

+ ··· + X

Solution: The formula for the MGF is almost trivial here,

(r) =

e

x

dx =



  r

for r < .

Since S

is the sum of n IID rv’s,

(r) =

⇥

(r)

⇤

✓



  r

◆

c) Find the Erlang density by starting with (2.15) and then calculating the marginal density for S

Solution: To ﬁnd the marginal density, f

), we start with the joint density in (2.15)

and integrate over the region of space where s

 s

 ···  s

. It is a peculiar integral,

since the integrand is constant and we are just ﬁnding the volume of the n 1 dimensional

space in s

, . . . , s

n1

with the inequality constraints above. For n = 2 and n = 3, we have

) = 

s

⇣



s

⌘

) = 

s





= 

s

⇣



s

⌘

剩余137页未读，继续阅读

weixin_43417896

粉丝: 0
资源: 1

Gallager《随机过程理论应用》习题精选解答

Stochastic Process 2nd edition

Stochastic Processes and Filtering Theory.pdf

def sgd(params,lr,batch_size): with torch.no_grad(): for param in params: param = lr* param.grad/batch_size param.grad.zero_()

ross s m. stochastic processes

请采用python以Tensorflow为架构编写《Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor》版本的SAC强化学习算法代码

请用python以Tensorflow为架构编写一个以这篇论文《Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor》依据的SAC强化学习完整代码

pytorch写一个vit

如何运行RNN进行训练的代码

robert g. gallager stochastic processes引用

感知器的三种算法用python呈现出来

stochastic models estimation and control.volume 1

rcwa_stochastic_optimizer针对的文献

AttributeError: module 'torchvision.ops' has no attribute 'stochastic_depth'

我想讲resnet和Swin-Transformer结合起来 先用resnet和se注意力模块 在用swin transformer。我用的是pytorch。请给下代码

利用随机梯度下降算法和小批量梯度下 降算法实现的Lasso回归代码，以及两种算法收敛过程图

最新资源

我想讲resnet和Swin-Transformer结合起来先用resnet和se注意力模块在用swin transformer。我用的是pytorch。请给下代码

利用随机梯度下降算法和小批量梯度下降算法实现的Lasso回归代码，以及两种算法收敛过程图