Advertisement
Guest User

Untitled

a guest
Jan 24th, 2019
80
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.25 KB | None | 0 0
  1. This is a one-player game. The goal of the game is to have N points.
  2. You start with zero points.
  3. You take a turn by rolling a six-sided die.
  4. On a 1, you gain 1 point.
  5. On a 6, you lose all points.
  6. On a 2, 3, 4, or 5, nothing happens.
  7.  
  8. On average, how many turns will it take you to reach N points?
  9. 6*((2^N)-1)
  10.  
  11.  
  12.  
  13. f(cur, n): the expected number of turns to the end of the game
  14.  
  15. if cur == n: 0
  16. else: (
  17. 1 + f(cur+1, n) +
  18. 1 + f(cur, n) +
  19. 1 + f(cur, n) +
  20. 1 + f(cur, n) +
  21. 1 + f(cur, n) +
  22. 1 + f(0, n)
  23. ) / 6
  24. == (6 + f(cur+1, n) + 4*f(cur, n) + f(0,n)) / 6
  25.  
  26.  
  27. let X = f(cur, n) when cur != n
  28. X = (6 + f(cur+1, n) + 4*X + f(0,n)) / 6
  29. 6*X = 6 + f(cur+1, n) + 4*X + f(0,n)
  30. 2*X = 6 + f(cur+1, n) + f(0,n)
  31. X = (6 + f(cur+1, n) + f(0,n)) / 2
  32. f(cur, n) = (6 + f(cur+1, n) + f(0,n)) / 2
  33.  
  34.  
  35. Let n == 4.
  36. Let Z = f(0,4)
  37. f(cur, n) = (Z + 6 + f(cur+1, n)) / 2
  38.  
  39. f(4,4) = 0.
  40. f(3,4) = (Z + 6) / 2 = Z/2 + 3
  41. f(2,4) = (Z + 6 + Z/2 + 3) / 2 = (3/4)*Z + 9/2
  42. f(1,4) = (Z + 6 + (3/4)*Z + 9/2) / 2 = ((7/4)*Z + 21/2) / 2 = ((7/8)*Z + 21/4)
  43. f(0,4) = Z = (Z + 6 + (7/8)*Z + 21/4) / 2
  44. 2*Z = Z + 6 + (7/8)*Z + 21/4
  45. Z = 6 + (7/8)*Z + 21/4
  46. (1/8)*Z = 6 + 21/4
  47. Z = (6 + 21/4)*8 = 48 + 42 = 90
  48.  
  49. WLOG, f(0, n) = uhhhhhhhh
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement