(from H. Shultz and B. Leonard19) A sequence of random numbers in [0, 1) is gene

Question

(from H. Shultz and B. Leonard19) A sequence of random numbers in [0, 1) is generated until the sequence is no longer monotone increasing. The num- bers are chosen according to the uniform distribution. What is the expected length of the sequence? (In calculating the length, the term that destroys monotonicity is included.) Hint: Let a 1, a2, be the sequence and let X denote the length of the sequence. Then P(X> k) P(a1 a2 ak) and the probability on the right-hand side is easy to calculate. Furthermore, one can show that E(X) 1 P(X 1) P(X >2)

Explanation / Answer

letus {x1,x2,x3,x4......xn} be the sample space

then

p(x=1) = 1 (single element is monotonically increasing)

p(x>1) = probebility that selected two in increasing order = 1/2

p(x >2) = probebility that selected three in increasing order = 1/3! = 1/6

p(x>3) = probebility that selected four in increasing order = 1/4!

hence

E(X) = 1 + p(x>1) + p(x>2) + .... = 1 + 1/2! + 1/3! + 1/4! + ....... = 1+ 1/1! + 1/2!+ 1/3! + .... -1

= e1 -1 = e-1 = 2.718281 - 1 = 1.718281

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

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