Question 4 (25 points) This question relates to simulations of i.i.d. numbers fr

Question

Question 4 (25 points) This question relates to simulations of i.i.d. numbers from 1, . M with the Alias method. Consider a mass function P on integers 1, . M. The alias decomposition allows decomposing P the following way . P(j)-, 1-1 Q(k)(j) for all j = 1, . . . , M. 1 AllQ are also mass functions on 1,... , M for all k . For each k there is at maximum one value of j such that J k and Q0)>0 Part (a), 10 points: Write an R function DecomposeAlias which takes as input . A vector P(1), . . . ,P(M)] where / P(j) = 1, and for J-1, , M we have px(1) [0,1] and outputs . An matrix of size M -1 x M whose kth row is Qlk), the kth probability measure given by the alias decomposition described above Part (b), 5 points: Consider a random variable X whose possible values are 1…·.10 (i.e. M- 10). Its mass function P is given by P(1) 0.05, P(2)-0.12, P(3)0.06. P(4)=0.11, P=0.07, P(6) = 0.13, P(7)=0.02, P(8)=0.20. P(9)=0.10, P(10)=0.14

Explanation / Answer

As a prelude to presenting the method for obtaining the following representation, there is a lemma as follows:

Let P=[Pi,i=1,...,n]P=[Pi,i=1,...,n] denote a probability mass function. Then

(a) There exists an i,1ini,1in, such that Pi<1(n1)Pi<1(n1), and

(b) For this i there exists a j,jij,ji, such that Pi+Pj1(n1)Pi+Pj1(n1)
The quantities PP,P(k)P(k),Q(k)Q(k), kn1kn1. represent probability mass functions on the integers 1,2,...,n1,2,...,n, that is they are n-vectors of nonnegative numbers summing to 1.

In addition, the vector P(k)P(k) has at most k nonzero components, and each of the Q(k)Q(k) has at most two nonzero components. We show that any probability mass function PP can be represented as an equally weighted mixture of n-1 probability mass functions QQ.

This means that we show, for suitably defined Q(1),...,Q(n1)Q(1),...,Q(n1), that PP can be expressed as
P=1/(n1)k=1n1Q(k)

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.