課程名稱︰機率 課程性質︰系必修 課程教師︰林守德 開課學院：電資學院 開課系所︰資工系 考試日期（年月日）︰2012/6/18 考試時限（分鐘）：180 mins 是否需發放獎勵金：是 （如未明確表示，則不予發放） 試題 : Probability 2012 Final Exam (Prof.Shou-de Lin) 6/18/12 14:30-17:30pm Total Points: 120 You can answer in either Chinese or Enflish 1. Please briefly describe the following concepeoremts. (16pts) (a) Law of large number (b) n-gram language model (c) Noisy channel model (d) Central Limit Theorem 2. Alice and Bob are communicating through a secret but unreliable channel. Now, Bob has received a sequence of digits: 1x435y2123zab12312456512c2412315d. There are some missing values marked with alphabet. Can you design a method, using the techniques taught in our probability class to estimate the missing value? (8pts) 3. In retrieval problem, assuming we only care about the ranking not the absolute score between a document and a query. Suppose we have Q as the normalized query vector of elngth k(e.g. (0.2, 0.3, 0.1, 0.4)) and documents (D1 to Di), each is the normalized i-th document vector of same length k. We want to rank the documents based on its similarity to the query using KL divergence and corss entropy(see the bottom for definition), please prove that the rankings of documents given query based on these two metrics are identical. (10pts) 4. Let U and V be two independent uniformly distributed random variables in the region [-10, 10]. Find the probability that the equation x^2+2Ux+V^2 have real roots? (6pts) 5. Suppose that X and Y are independent exponential random variables with parameter λ, and let Z = X/(X+Y), show that Z is a uniform distribution over(0,1). (10 pts) 6. Let X be a discrete random variable and Y is a function of X. For each of the following case, please answer whether H(X) or H(Y) is larger. (8pts) (a) Y = (X-2)^2 + 3 (4 pts) (b) Y = tanX (4 pts) 7. Let {x1, X2, ..., Xn} are integers, generated by random round-off sampling from a uniform distribution U[0, b]. Now we want to estimate the parameters b, this is known as German tank problem in WWII. (Sample are the German tank serial numbers spot by the Allies, and we want to estimate total number of tanks German has) (5*3=15 pts) (a) find the estimation of parameters b using Maximum Likelihood Estimation. (b) Find the estimation of parameters b using Method of Moments. (c) What are the potential concerns for each of the estimation? 8. A dog walks on the integers, possibly reversing direction at each step with probability p = 0.1. Let Xi be the ith position of the dog, and X0 = 0(starts at origin). The first step is equally likely to be positive or negative. For example, a walk might look like this: (X0, X1, X2, ...) = (0, -1, -2, -3, -4, -3, -2, -1, 0, 1). In this example the dog reverses its direction after X4. (15pts) (a)Find H(X0, X1, X2, ... Xn) (hint: chain rule, 10 pts) (b)What is the expected number of steps the dog takes before reversing direction? (5 pts) 9. (Revisit Midterm II) Let X~N(μ,σ^2), a lognormal distribution is Y: log(Y)~X. What is the mean and variance of Y? (8 pts) 10. A statistic department at a large university maintains at tutoring service for students. The hypothesis is that 40% of the students that using this service would be from business department, 30% from engineering department, 20% from social science department and 10% from agriculture. A random sample of 120 students revealed that 52, 38, 21, 9 students were from each department, respectively. Using Chi-square test to check whether the sampling results follow the hypothesis with α=0.05 (10pts) 11. For each problem below, show that it is TRUE or FALSE. If it is true, prove it. Otherwise, give an example. U and V are independent random variables. Let X=f(U) and Y=f(U)+V. Then, (14pts) (a) If f is an one-to-one function, is it true that I(X;Y)=I(U;Y)? (b) If f is an many-to-one function, is it true that I(X;Y)=I(U;Y)? Appendix: Exponential Distribution Normal Distribution Cross entropy: H(p, q) = -Σx p(x)log(q(x)) KL divergence: DKL(P||Q) = Σi P(i)ln(P(i)/Q(i)) Chi-square table --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.30.130