Dynamic Programming: Two coins X and Y Flip coin X: gain 1 point for the head, and lose 1 point for the tail Flip coin Y: gain 3 points for the head, lose 3 points for the tail. After n round, if the final score is positive, you win. Otherwise, you lose. The score does not matter. Pr(s) be the probability of winning; r is the round; s is the score. P0(s) = 1 for s >= 1; P0(s) = 0 if s <= 0. a. Explain why P1(s) = 0 when s <= -3; P1(s) = 0.5 when -2 <= s <= 1; P1(s) = 1 for s >= 2. b. Explain why you must select X if s is 2 or 3, and you must select Y if s is −2 or −1. b. Determine P2(s) for each possible value of s and explain. (each probability will be one of 0, ¼, 1/2, ¾, 1) c. Fine a recurrence relation for Pr(s) with form Pr(s) = max[(?+?)/2, (?+?)/2]. Explain. d. Use Dynamic Programming to compute probability P100(0) (win the game if it has 100 rounds).
Dynamic
Two coins X and Y
Flip coin X: gain 1 point for the head, and lose 1 point for the tail
Flip coin Y: gain 3 points for the head, lose 3 points for the tail.
After n round, if the final score is positive, you win. Otherwise, you lose. The score does not matter.
Pr(s) be the probability of winning; r is the round; s is the score.
P0(s) = 1 for s >= 1; P0(s) = 0 if s <= 0.
a. Explain why P1(s) = 0 when s <= -3; P1(s) = 0.5 when -2 <= s <= 1; P1(s) = 1 for s >= 2.
b. Explain why you must select X if s is 2 or 3, and you must select Y if s is −2 or −1.
b. Determine P2(s) for each possible value of s and explain. (each probability will be one of 0, ¼, 1/2, ¾, 1)
c. Fine a recurrence relation for Pr(s) with form Pr(s) = max[(?+?)/2, (?+?)/2]. Explain.
d. Use Dynamic Programming to compute probability P100(0) (win the game if it has 100 rounds).
Trending now
This is a popular solution!
Step by step
Solved in 3 steps with 2 images
