Wout12345

Birthday problem variants script

Sep 9th, 2022
87
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.43 KB | None | 0 0
  1. # Made by Wout12345
  2.  
  3. import numpy as np
  4. import matplotlib.pyplot as plt
  5.  
  6. days = 365
  7. n = 61
  8. min_pairs = 5
  9.  
  10. experiments = int(1e6)
  11. passes = 0
  12. probabilities = np.empty(dtype=np.float32, shape=(experiments,))
  13.  
  14. # Some helper variables for blocking
  15. block_size = int(1e5)
  16. experiments = int(np.ceil(experiments/block_size))*block_size
  17.  
  18. # Initialize constant indices in birthdays array
  19. random_birthdays_amount = block_size*n
  20. birthdays = np.empty(dtype=np.uint32, shape=(2, random_birthdays_amount))
  21. for i in range(block_size):
  22. for j in range(n):
  23. birthdays[0, i*n + j] = i
  24.  
  25. birthday_counts = np.empty(dtype=np.uint32, shape=(block_size, days))
  26. success = np.empty(dtype=np.uint8, shape=(block_size,))
  27.  
  28. for i in range(0, experiments, block_size):
  29.  
  30. # Assign random birthdays
  31. birthdays[1, :] = np.random.randint(0, days - 1, (random_birthdays_amount,))
  32.  
  33. # Count number of birthdays per day
  34. birthday_counts.fill(0)
  35. np.add.at(birthday_counts, (birthdays[0, :], birthdays[1, :]), 1)
  36.  
  37. # Check if there are at least 4 pairs of people sharing their birthday without 3 or more people ever sharing a birthday
  38. success.fill(1)
  39. #success[np.amax(birthday_counts, axis=1) > 2] = 0
  40. success[np.sum((birthday_counts >= 2).astype(int), axis=1) < min_pairs] = 0
  41.  
  42. # success has now been determined
  43. probabilities[i:i + block_size] = (round(probabilities[i - 1]*i) if i > 0 else 0) + np.cumsum(success)
  44. probabilities[i:i + block_size] /= np.linspace(i + 1, i + block_size, block_size)
  45.  
  46. print("Empirical probability after %s experiments: %.8f"%(experiments, probabilities[-1]))
  47.  
  48. # The part below is only relevant if you have some theoretical value you want to verify
  49. theoretical_probability = 0.1720784820786103795516077320188488593260442214894743886987922653 # For exactly 4 pairs
  50. #theoretical_probability = 0.76 # For 4+ pairs normally
  51. print("Relative error from theoretical probability: %s"%((probabilities[-1] - theoretical_probability)/theoretical_probability))
  52.  
  53. """
  54. plt.plot(range(1, experiments+1), probabilities)
  55. plt.plot([1, experiments], [theoretical_probability,]*2)
  56. plt.xlabel("Experiments")
  57. plt.ylabel("Probability")
  58. plt.xlim(1, experiments)
  59. plt.ylim(0, 1)
  60. plt.show()
  61.  
  62. plt.plot(range(1, experiments+1), np.abs(probabilities - theoretical_probability))
  63. plt.xscale("log", base=2)
  64. plt.yscale("log", base=2)
  65. plt.xlabel("Experiments")
  66. plt.ylabel("Error of empirical probability")
  67. plt.xlim(1, experiments)
  68. plt.grid()
  69. plt.show()
  70. """
Advertisement
Add Comment
Please, Sign In to add comment