e06_birthday_problem.sagews

#what is the probability that at least one pair of n students has the same birthday?
#how many students do you need in order for the probability to be at least 0.5?

#given n, we need to guess n random birthdays
#(we'll assume that birthdays are uniformly distributed - not true in real life)
#instead of guessing jan.1, nov. 14, etc, we can just use numbers 1 to 365
#can use randint
randint(1,365)

22

n = 5
guess = [randint(1,365) for i in [1..n]]

range(5)

[0, 1, 2, 3, 4]

range(2,6)

[2, 3, 4, 5]

guess

[244, 233, 226, 66, 354]

#after we make a guess, we need to check is there's a pair of numbers that's the same
for i in range(n):
    for j in range(n):
        if j > i and guess[i] == guess[j]:
            print "Bingo!"

#repeat this experiment *many* (how many?) times and collect data
#then the empirical probability of a pair of n studnets having the same birthday
#*is* the (number of successes) / (number of experiments)

L=[5,6,7,6]
S=Set(L)
L
S
#if a list on integers has a pair that the same,
#the corresponding set will have fewer elements
len(L)
len(S)

[5, 6, 7, 6] {5, 6, 7} 4 3

n = 23
#guess of n random birthdays
birthdays = [randint(1,365) for i in [1..n]]
birthdays
#test if there's a piar that the same by testing if the Set of birthdays is smaller than the List of birthdays
if len(Set(birthdays)) < len(birthdays):
    print "Bingo!"

[23, 113, 3, 160, 179, 285, 228, 119, 59, 34, 197, 171, 265, 349, 311, 54, 126, 165, 149, 102, 155, 23, 101] Bingo!

def birthday_test(n):
    successes = 0
    for i in [1..1000]:
        birthdays = [randint(1,365) for i in [1..n]]
        if len(Set(birthdays)) < len(birthdays):
            successes = successes + 1
    return successes/1000

birthday_test(5)

0.0210000000000000

birthday_test(23)

0.505000000000000

birthday_test(77)

1.00000000000000

birthday_test(366)

1.00000000000000

birthday_test(1)

0.000000000000000

#is there is problem? it can't be probability  effectively 1 for only 77 stdents, can it?!?!?!
#can't use plot as our function is only defined for positive integers
#so let's get 365 data points and use scatter plot
data = [(x, birthday_test(x)) for x in [1..366]]

Error in lines 1-1 Traceback (most recent call last): File "/projects/sage/sage-7.5/local/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 982, in execute exec compile(block+'\n', '', 'single') in namespace, locals File "", line 1, in <module> File "", line 4, in birthday_test File "/projects/sage/sage-7.5/local/lib/python2.7/site-packages/sage/misc/prandom.py", line 125, in randint return _pyrand().randint(a, b) File "/projects/sage/sage-7.5/local/lib/python/random.py", line 242, in randint return self.randrange(a, b+1) File "src/cysignals/signals.pyx", line 252, in cysignals.signals.python_check_interrupt (build/src/cysignals/signals.c:2854) File "src/cysignals/signals.pyx", line 97, in cysignals.signals.sig_raise_exception (build/src/cysignals/signals.c:1303) KeyboardInterrupt

for i in [1..365]:
    print i, birthday_test(i)

1 0.000000000000000 2 0.00400000000000000 3 0.0120000000000000 4 0.0200000000000000 5 0.0260000000000000 6 0.0410000000000000 7 0.0580000000000000 8 0.0860000000000000 9 0.104000000000000 10 0.127000000000000 11 0.136000000000000 12 0.191000000000000 13 0.179000000000000 14 0.244000000000000 15 0.255000000000000 16 0.275000000000000 17 0.308000000000000 18 0.343000000000000 19 0.377000000000000 20 0.412000000000000 21 0.436000000000000 22 0.488000000000000 23 0.524000000000000 24 0.544000000000000 25 0.562000000000000 26 0.598000000000000 27 0.625000000000000 28 0.662000000000000 29 0.706000000000000 30 0.693000000000000 31 0.747000000000000 32 0.749000000000000 33 0.774000000000000 34 0.798000000000000 35 0.814000000000000 36 0.836000000000000 37 0.849000000000000 38 0.859000000000000 39 0.880000000000000 40 0.890000000000000 41 0.891000000000000 42 0.927000000000000 43 0.927000000000000 44 0.937000000000000 45 0.942000000000000 46 0.957000000000000 47 0.962000000000000 48 0.970000000000000 49 0.964000000000000 50 0.962000000000000 51 0.979000000000000 52 0.979000000000000 53 0.981000000000000 54 0.986000000000000 55 0.990000000000000 56 0.990000000000000 57 0.990000000000000 58 0.995000000000000 59 0.997000000000000 60 0.996000000000000 61 0.995000000000000 62 0.997000000000000 63 0.995000000000000 64 0.998000000000000 65 0.998000000000000 66 0.998000000000000 67 0.999000000000000 68 1.00000000000000 69 0.997000000000000 70 0.997000000000000 71 1.00000000000000 72 1.00000000000000 73 1.00000000000000 74 0.999000000000000 75 1.00000000000000 76 1.00000000000000 77 0.999000000000000 78 1.00000000000000 79 1.00000000000000 80 1.00000000000000 81 1.00000000000000 82 1.00000000000000 83 1.00000000000000 84 1.00000000000000 85 1.00000000000000 86 1.00000000000000 87 1.00000000000000 88 1.00000000000000 89 1.00000000000000 90 1.00000000000000 91 1.00000000000000 92 1.00000000000000 93 1.00000000000000 94 1.00000000000000 95 1.00000000000000 96 1.00000000000000 97 1.00000000000000 98 1.00000000000000 99 1.00000000000000 100 1.00000000000000 101 1.00000000000000 102 1.00000000000000 103 1.00000000000000 104 1.00000000000000 105 1.00000000000000 106 1.00000000000000 107 1.00000000000000 108 1.00000000000000 109 1.00000000000000 110 1.00000000000000 111 1.00000000000000 112 1.00000000000000 113 1.00000000000000 114 1.00000000000000 115 1.00000000000000 116 1.00000000000000 117 1.00000000000000 118 1.00000000000000 119 1.00000000000000 120 1.00000000000000 121 1.00000000000000 122 1.00000000000000 123 1.00000000000000 124 1.00000000000000 125 1.00000000000000 126 1.00000000000000 127 1.00000000000000 128 1.00000000000000 129 1.00000000000000 130 1.00000000000000 131 1.00000000000000 132 1.00000000000000 133 1.00000000000000 134 1.00000000000000 135 1.00000000000000 136 1.00000000000000 137 1.00000000000000 138 1.00000000000000 139 1.00000000000000 140 1.00000000000000 141 1.00000000000000 142 1.00000000000000 143 1.00000000000000 144 1.00000000000000 145 1.00000000000000 146 1.00000000000000 147 1.00000000000000 148 1.00000000000000 149 1.00000000000000 150 1.00000000000000 151 1.00000000000000 152 1.00000000000000 153 1.00000000000000 154 1.00000000000000 155 1.00000000000000 156 1.00000000000000 157 1.00000000000000 158 1.00000000000000 159 1.00000000000000 160 1.00000000000000 161 1.00000000000000 162 1.00000000000000 163 1.00000000000000 164 1.00000000000000 165 1.00000000000000 166 1.00000000000000 167 1.00000000000000 168 1.00000000000000 169 1.00000000000000 170 1.00000000000000 171 1.00000000000000 172 1.00000000000000 173 1.00000000000000 174 1.00000000000000 175 1.00000000000000 176 1.00000000000000 177 1.00000000000000 178 1.00000000000000 179 1.00000000000000 180 1.00000000000000 181 1.00000000000000 182 1.00000000000000 183 1.00000000000000 184 1.00000000000000 185 1.00000000000000 186 1.00000000000000 187 1.00000000000000 188 1.00000000000000 189 1.00000000000000 190 1.00000000000000 191

Error in lines 1-2 Traceback (most recent call last): File "/projects/sage/sage-7.5/local/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 982, in execute exec compile(block+'\n', '', 'single') in namespace, locals File "", line 2, in <module> File "", line 4, in birthday_test File "src/cysignals/signals.pyx", line 252, in cysignals.signals.python_check_interrupt (build/src/cysignals/signals.c:2854) File "src/cysignals/signals.pyx", line 97, in cysignals.signals.sig_raise_exception (build/src/cysignals/signals.c:1303) KeyboardInterrupt

data = []
for i in [1..365]:
    result = birthday_test(i)
    print i, result
    data.append((i,result))

scatter_plot(data)

%lisp
(+ 5 (- 9 3))

11

#n is the number of students
#experiments is the number of experiments performed
def birthday_test2(n, experiments):
    successes = 0
    for i in [1..experiments]:
        birthdays = [randint(1,365) for i in [1..n]]
        if len(Set(birthdays)) < len(birthdays):
            successes = successes + 1
    return successes/experiments

#what is the probability that some pair of 10 students have the same birthday?
#n is the number of students
#experiments is the number of experiments performed
birthday_test2(10, 1000)

121/1000

birthday_test2(10, 1)

0

data = [(x,birthday_test2(10,x)) for x in [1..100]]

scatter_plot(data)

data = [(x,birthday_test2(10,x)) for x in [1..1000]]

scatter_plot(data)

birthday_test2(10, 100000)

367/3125

n(_)

0.117440000000000

#n is the number of students
#experiments is the number of experiments performed
#len(Set(birthdays)) < len(birthdays)-1 means *either* 3 students have the same birthday or 2 different pairs of students share the same birthday
def birthday_test3(n, experiments):
    successes = 0
    for i in [1..experiments]:
        birthdays = [randint(1,365) for i in [1..n]]
        if len(Set(birthdays)) < len(birthdays)-1:
            successes = successes + 1
    return successes/experiments

data = []
for i in [1..365]:
    result = birthday_test3(i,100)
    print i, result.n()

    data.append((i,result))

1 0.000000000000000 2 0.000000000000000 3 0.000000000000000 4 0.000000000000000 5 0.000000000000000 6 0.000000000000000 7 0.0100000000000000 8 0.000000000000000 9 0.000000000000000 10 0.000000000000000 11 0.0300000000000000 12 0.000000000000000 13 0.0100000000000000 14 0.0200000000000000 15 0.0300000000000000 16 0.0400000000000000 17 0.0400000000000000 18 0.110000000000000 19 0.130000000000000 20 0.0800000000000000 21 0.0900000000000000 22 0.170000000000000 23 0.100000000000000 24 0.140000000000000 25 0.210000000000000 26 0.250000000000000 27 0.210000000000000 28 0.290000000000000 29 0.380000000000000 30 0.370000000000000 31 0.310000000000000 32 0.400000000000000 33 0.350000000000000 34 0.410000000000000 35 0.480000000000000 36 0.500000000000000 37 0.600000000000000 38 0.520000000000000 39 0.570000000000000 40 0.600000000000000 41 0.630000000000000 42 0.700000000000000 43 0.680000000000000 44 0.750000000000000 45 0.780000000000000 46 0.780000000000000 47 0.820000000000000 48 0.840000000000000 49 0.780000000000000 50 0.830000000000000 51 0.810000000000000 52 0.950000000000000 53 0.890000000000000 54 0.900000000000000 55 0.900000000000000 56 0.950000000000000 57 0.940000000000000 58 0.970000000000000 59 0.990000000000000 60 0.980000000000000 61 0.970000000000000 62 0.930000000000000 63 0.970000000000000 64 0.970000000000000 65 0.980000000000000 66 0.970000000000000 67 0.990000000000000 68 1.00000000000000 69 1.00000000000000 70 1.00000000000000 71 1.00000000000000 72 0.990000000000000 73 1.00000000000000 74 1.00000000000000 75 0.990000000000000 76 1.00000000000000 77 1.00000000000000 78 1.00000000000000 79 1.00000000000000 80 1.00000000000000 81 1.00000000000000 82 1.00000000000000 83 1.00000000000000 84 1.00000000000000 85 1.00000000000000 86 1.00000000000000 87 1.00000000000000 88 1.00000000000000 89 1.00000000000000 90 1.00000000000000 91 1.00000000000000 92 1.00000000000000 93 1.00000000000000 94 1.00000000000000 95 1.00000000000000 96 1.00000000000000 97 1.00000000000000 98 1.00000000000000 99 1.00000000000000 100 1.00000000000000 101 1.00000000000000 102 1.00000000000000 103 1.00000000000000 104 1.00000000000000 105 1.00000000000000 106 1.00000000000000 107 1.00000000000000 108 1.00000000000000 109 1.00000000000000 110 1.00000000000000 111 1.00000000000000 112 1.00000000000000 113 1.00000000000000 114 1.00000000000000 115 1.00000000000000 116 1.00000000000000 117 1.00000000000000 118 1.00000000000000 119 1.00000000000000 120 1.00000000000000 121 1.00000000000000 122 1.00000000000000 123 1.00000000000000 124 1.00000000000000 125 1.00000000000000 126 1.00000000000000 127 1.00000000000000 128 1.00000000000000 129 1.00000000000000 130 1.00000000000000 131 1.00000000000000 132 1.00000000000000 133 1.00000000000000 134 1.00000000000000 135 1.00000000000000 136 1.00000000000000 137 1.00000000000000 138 1.00000000000000 139 1.00000000000000 140 1.00000000000000 141 1.00000000000000 142 1.00000000000000 143 1.00000000000000 144 1.00000000000000 145 1.00000000000000 146 1.00000000000000 147 1.00000000000000 148 1.00000000000000 149 1.00000000000000 150 1.00000000000000 151 1.00000000000000 152 1.00000000000000 153 1.00000000000000 154 1.00000000000000 155 1.00000000000000 156 1.00000000000000 157 1.00000000000000 158 1.00000000000000 159 1.00000000000000 160 1.00000000000000 161 1.00000000000000 162 1.00000000000000 163 1.00000000000000 164 1.00000000000000 165 1.00000000000000 166 1.00000000000000 167 1.00000000000000 168 1.00000000000000 169 1.00000000000000 170 1.00000000000000 171 1.00000000000000 172 1.00000000000000 173 1.00000000000000 174 1.00000000000000 175 1.00000000000000 176 1.00000000000000 177 1.00000000000000 178 1.00000000000000 179 1.00000000000000 180 1.00000000000000 181 1.00000000000000 182 1.00000000000000 183 1.00000000000000 184 1.00000000000000 185 1.00000000000000 186 1.00000000000000 187 1.00000000000000 188 1.00000000000000 189 1.00000000000000 190 1.00000000000000 191 1.00000000000000 192 1.00000000000000 193 1.00000000000000 194 1.00000000000000 195 1.00000000000000 196 1.00000000000000 197 1.00000000000000 198 1.00000000000000 199 1.00000000000000 200 1.00000000000000 201 1.00000000000000 202 1.00000000000000 203 1.00000000000000 204 1.00000000000000 205 1.00000000000000 206 1.00000000000000 207 1.00000000000000 208 1.00000000000000 209 1.00000000000000 210 1.00000000000000 211 1.00000000000000 212 1.00000000000000 213 1.00000000000000 214 1.00000000000000 215 1.00000000000000 216 1.00000000000000 217 1.00000000000000 218 1.00000000000000 219 1.00000000000000 220 1.00000000000000 221 1.00000000000000 222 1.00000000000000 223 1.00000000000000 224 1.00000000000000 225 1.00000000000000 226 1.00000000000000 227 1.00000000000000 228 1.00000000000000 229 1.00000000000000 230 1.00000000000000 231 1.00000000000000 232 1.00000000000000 233 1.00000000000000 234 1.00000000000000 235 1.00000000000000 236 1.00000000000000 237 1.00000000000000 238 1.00000000000000 239 1.00000000000000 240 1.00000000000000 241 1.00000000000000 242 1.00000000000000 243 1.00000000000000 244 1.00000000000000 245 1.00000000000000 246 1.00000000000000 247 1.00000000000000 248 1.00000000000000 249 1.00000000000000 250 1.00000000000000 251 1.00000000000000 252 1.00000000000000 253 1.00000000000000 254 1.00000000000000 255 1.00000000000000 256 1.00000000000000 257 1.00000000000000 258 1.00000000000000 259 1.00000000000000 260 1.00000000000000 261 1.00000000000000 262 1.00000000000000 263 1.00000000000000 264 1.00000000000000 265 1.00000000000000 266 1.00000000000000 267 1.00000000000000 268 1.00000000000000 269 1.00000000000000 270 1.00000000000000 271 1.00000000000000 272 1.00000000000000 273 1.00000000000000 274 1.00000000000000 275 1.00000000000000 276 1.00000000000000 277 1.00000000000000 278 1.00000000000000 279 1.00000000000000 280 1.00000000000000 281 1.00000000000000 282 1.00000000000000 283 1.00000000000000 284 1.00000000000000 285 1.00000000000000 286 1.00000000000000 287 1.00000000000000 288 1.00000000000000 289 1.00000000000000 290 1.00000000000000 291 1.00000000000000 292 1.00000000000000 293 1.00000000000000 294 1.00000000000000 295 1.00000000000000 296 1.00000000000000 297 1.00000000000000 298 1.00000000000000 299 1.00000000000000 300 1.00000000000000 301 1.00000000000000 302 1.00000000000000 303 1.00000000000000 304 1.00000000000000 305 1.00000000000000 306 1.00000000000000 307 1.00000000000000 308 1.00000000000000 309 1.00000000000000 310 1.00000000000000 311 1.00000000000000 312 1.00000000000000 313 1.00000000000000 314 1.00000000000000 315 1.00000000000000 316 1.00000000000000 317 1.00000000000000 318 1.00000000000000 319 1.00000000000000 320 1.00000000000000 321 1.00000000000000 322 1.00000000000000 323 1.00000000000000 324 1.00000000000000 325 1.00000000000000 326 1.00000000000000 327 1.00000000000000 328 1.00000000000000 329 1.00000000000000 330 1.00000000000000 331 1.00000000000000 332 1.00000000000000 333 1.00000000000000 334 1.00000000000000 335 1.00000000000000 336 1.00000000000000 337 1.00000000000000 338 1.00000000000000 339 1.00000000000000 340 1.00000000000000 341 1.00000000000000 342 1.00000000000000 343 1.00000000000000 344 1.00000000000000 345 1.00000000000000 346 1.00000000000000 347 1.00000000000000 348 1.00000000000000 349 1.00000000000000 350 1.00000000000000 351 1.00000000000000 352 1.00000000000000 353 1.00000000000000 354 1.00000000000000 355 1.00000000000000 356 1.00000000000000 357 1.00000000000000 358 1.00000000000000 359 1.00000000000000 360 1.00000000000000 361 1.00000000000000 362 1.00000000000000 363 1.00000000000000 364 1.00000000000000 365 1.00000000000000