課程名稱︰應用隨機過程
課程性質︰選修
課程教師︰呂學一
開課學院：電資學院
開課系所︰資工所、生醫電資所
考試日期（年月日）︰2012.04.19
考試時限（分鐘）：180
試題 :
台大資工 隨機過程 期中考
2012年4月19日 下午兩點廿分起三個小時
說明：共八題，每題十五分，可按任何順序答題。
每題難度不同，審慎判斷恰當的解題順序。
第一題
圍棋盒子中有大量的黑白棋子，我們不斷地在把棋盒攪拌均勻之後取出一枚棋子，記錄其
顏色，然後放回棋盒中。記錄了一陣子之後，統計發現每次取出白子之後，接下那枚棋子
的顏色有3/7為白，4/7為黑；每次取出黑子之後，接下那枚棋子的顏色有2/5為黑，3/5為
白。請估計棋盒中黑子的比例為何？
第二題
Let Χ be a finite irreducible aperiodic Markov chain with n states. Define
the following four concepts and describe their relation.
˙vector of limiting probabilities of Χ,
˙stationary distribution of Χ,
˙vector of long-run proportions of Χ, and
˙vector of expected return times of Χ.
第三題
Let Χ be an irreducible finite Markov chain with n states. For each
i = 1, 2, ... , n, let r_i be the long-run proportion of state i. Prove that
the row vector r = (r_1, r_2, ... , r_n) satisfies r × Ρ = r, where Ρ is
the matrix of transition probabilities of X.
第四題
Consder the Markov chain Χ of gambler's ruin with four states {0, 1, 2, 3},
where 0 and 3 are the absorbing states. Let X(0) = 2. Please compute the
expected number of time indices, including time 0, in which Χ stays in state
1 or 2.
第五題
在一個 branching process 裡，每個 life form 各有l/3的機率有0,l,2個 offsprings。
如果一開始有100個 llfe forms，請問這個群體最後絕種的機率為何？
第六題
老鼠在九個節點的「田」字形的迷宮裡跑來跑去，每單位時問，從目前的位置，根據等機
率的方式跑到到相鄰的點上去。請證明這個跑來跑去的過程是一個 time-reversible
Markov chain。也請計算長時間下來，老鼠在這九個節點的機率分別為何。
第七題
Sample space S consists of the permutations x = (x_1, x_2, ... , x_n) of
{1, 2, ... , n} satisfying
n^3
Σ i．x_i < ───.
1≦i≦n 4
Suppose that for each permutation x of S, the probability of x is
h(x) / Σ h(x) , where function h(x) = Σ (x_i / i). Please describe how
x∈S 1≦i≦n
to estimate the expectation of
f(x) = Σ (i^2)．x_i
1≦i≦n
over all permutations x ∈ S using Hastings-Metropolis's approach.
第八題 n m
Let i and j be two distinct states of Ｘ such that Ｐ [i, j]．P [j, i] > 0
holds for some positive integers m and n. Prove that if i is transient, then
j is also transient.