课程名称︰应用随机过程
课程性质︰选修
课程教师︰吕学一
开课学院：电资学院
开课系所︰资工所、生医电资所
考试日期（年月日）︰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.