Consider the following recursive algorithm TwoTails, which takes as input a posi

Question

Consider the following recursive algorithm TwoTails, which takes as input a positive integer k: Algorithm TWOTAILS(/c): // all coin flips made are mutually independent flip a fair coin twice; if the coin came up heads exactly twice then return 2^k else Two Tails (k + 1) endif You run algorithm TwoTails(1). i.e., with k = 1. Define the random variable X to be the value of the output of this algorithm. Let k Greaterthanorequalto 1 be an integer. What is Pr(X = 2^k)? (1/4)^k middot 3/4 (1/4)^k - 1 middot 3/4 (3/4)^k middot 1/4 (3/4)^k - 1 middot 1/4

Explanation / Answer

Answer:

When two two coins are flipped the probability of getting success that is getting two heads is always 1/4.

P(Success= S) = 1/4 and P(Failure = F) = 3/4 . When we run the algorithm Two Tails(1)

The above process runs until there is one stop and the process will have the pattern like this X=2k if and only if there are only k-1 failures preceeding one success

P(X=2k) = P( Fk-1 S1)

               Since the tails are mutually independent, we can wirte

               = P(Fk-1) P(S)

               = P(F).P(F).P(F). . . .P(F) (k-1 times)    P(S)

               = (3/4).(3/4).(3/4). . . (3/4) (k-1 times)   (1/4)

P(X=2k) = (3/4)k-1(1/4)

So the correct option is (d)

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

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