課程名稱︰應用隨機過程
課程性質︰選修
課程教師︰呂學一
開課學院：電資學院
開課系所︰資工所、生醫電資所
考試日期（年月日）︰2012.06.21
考試時限（分鐘）：180
試題 :
台大資工 隨機過程 期末考
2012年6月21日 下午兩點廿分起三個小時
說明：共十二題，每題十分，可按任何順序答題。
每題難度不同，審慎判斷恰當的解題順序。
第一題
請定義何謂 Poisson process，並請說明為甚麼它是一種 continuous-time Markov
chain。
第二題
A server works for an exponentially distributed time with rate μ and then
fails. A TA checks the server at times distributed according to a Poisson
process with rate λ. If the server is found to have failed, then it is
immediately replaced. Find the expected time between two replacements of
servers.
第三題
Customers arrive at a two-server service station according to a Poisson process
with rate λ. Whenever a new customer arrives, any customer in the system
immediately leaves. A new arrival enters service first with server 1 and then
with server 2. Suppose that the service times at the servers are independent
exponentials with respective rates μ_1 and μ_2. Compute the probability that
an entering customer completes the whole service process.
第四題
貓味抓到老鼠的過程是個 Poisson process with rate λ。老鼠有黑、灰、白三種，出
現的機率分別為0.6、0.3、0.1。請證明貓味完整收集三種老鼠所需時間的期望值，洽好
等於完整收集到三種老鼠時總共抓到老鼠數量之期望值的1/λ倍。
第五題
Power surges occur according to a Poisson process with rate λ, and each surge
independently causes our server to fail with probability p. Let T be the time
at which the server fails and let N be the number of surges that a server
failure takes.
(a) Explain why the distribution of T conditioned on N = n is a gamma with
parameter (n, λ).
(b) Explain why the distribution of N conditioned on T = t is 1 plus a
Poisson with parameter λ(1 - p)t.
第六題
Consider a non-homogeneous Poisson process whose intensity function λ(t) is
upper-bounded by some finite number λ. Argue that such a process is equivalent
to a process of "counted events" from a (homogeneous) Poisson process with
rate λ, where an event at time t is "counted" (independent of the past) with
probability λ(t)/λ.
第七題
Consider two servers maintained by one TA. For each i = 1, 2, server i
functions for an exponential time with rate μ_i. The repair time for either
server is exponential with parameter μ. Can we analyze this as a
birth-and-death process? If so, what are the parameters (i.e., birth rate β_i
and death rate δ_i for each integral state i)? If not, how do we characterize
this continuous-time Markov chain? (That is, what are the state space, the
transition rate λ_i of each state i, and the transition probability Ｐ[i, j]
for any two distinct states i and j?)
第八題
There are n individuals in a population, some of whom have a certain infection
that spreads as follows. Contacts between two members of this population occur
in accordance with a Poisson process having rate λ. When a contact occurs, it
╭n╮
is equally likely to involve any of the │ │ pairs of individuals in the
╰2╯
population. If a contact involves an infected and a noninfected individual,
then with probability p the noninfected individual becomes infected. Once
infected, an individual remains infected throughout. Let X(t) denote the
number of infected members of the population at time t. Let X(0) = 1. What is
the expected length of time when all n individuals of the population are
infected.
第九題
Prove Kolmogorov's backward differential equation
P' (t) = Σ q P (t) - λ P (t)
i,j k∈S ik kj i ij
for finite continuous-time Markov chain.
第十題
Consider a taxi station where taxis and customers arrive in accordance with
Poisson processes with respective rates of 1 and 2 per minute. A taxi will
wait no matter how many other taxis are present. However, an arriving customer
who does not find a taxi waiting leaves. Find
(a) the expected number of taxis waiting, and
(b) the long-run proportion of arriving customers who get taxis.
第十一題
Explain why an irreducible positive recurrent continuous-time Markov chain Ｘ
is time-reversible if π_i．q_ij = π_j．q_ji holds for any two states i and j
of Ｘ, where π_i (respectively, π_j) is the limiting probability of state i
(respectively, j) and q_ij (respectively, q_ji) is the instantaneous rate of
i-to-j (respectively, j-to-i) transitions.
第十二題
Characterize the uniformized version of the continuous-time Markov chain of
第七題.