GB-Stochastic-Algorithms

Question 1

Gambler’s ruin problem: Player M has $1 and Player N has $2. Each game gives the winner $1 from the other. As a better player, M wins 2/3 of the games. They play until one of them is bankrupt. What is the probability that M wins?

Answer 1

• Let a1 be the probability that player M wins
• Let a2 be defined as where there is back and forth between player loosing and winning between $1 and $2
• a1 = 1/3 * 0 + 2/3a2
• a2 = 1/3*a1 + 2/3*1
• Plug a2 into a1
• a1 = 2/3*(1/3*a1 + 2/3) = 2/9a1 + 4/9
• a1 = 4/7 (probability of M winning)

Question 2

Two players bet on rolls of the total of two standard six-face dice. Player A bets that sum of 12 will occur first. Player B bets that two consecutive 7s will occur fist. What is the probability A will win?

Answer 2

• Probabilty that sum is 12, 1/36
• Probability that the sum is 7:
  
  • 6/36
• as = (1/36)*1 + (6/36)a7 + (29/36)*as
• a7 = (1/36)*1 + (6/36)*0 + (29/36)*as
  
  • Why 0, because we care about A winning (which is the sum = 12)
• Solve the above equation and we will get 7/13

Question 3

A casino comes up with a fancy game. It allows you to roll a dice as many times as you want unless a 6 appears. After each roll - if 1 appears, you will win $1, if 2 appears, you wil win $2 etc. If 6 appears, you will loose all the money you have earned and the game stop. After each roll - you can decide to keep the money or call it a quit, how much are you willing to pay for this game?

Answer 3

• Assume that we have accumulated x dollars
• The decision to have another roll depends on the expected profit vs. expected loss.
• 1/6(n+1) + 1/6(n+2) + 1/6(n+3)..+1/6(n+5) + 1/6*0 = 5/6n + 2.5
• In a spreadsheet, column for 1 to 19, and create another column with the above equation. You see that when it hits 14, the expected profit is greater and you should stop. At this stage if you want to play, to play this game, you should be willing to pay:
  
  • 1/6*(Sum 1 to 5) E(f(n+i))
• Solve this problem recursively, you will receive the answer of 6.15

Question 4

How do you swap two integers i and j without using additional storage space?

Answer 4

• i = i + j
• j = i - j
• i = i - j