Programs run into luck too. Two randomly made IDs can happen to be the same, and the same linear search can finish early or late depending on where the value is. We can’t know in advance, but by counting cases we can put a number on how often things collide and how many steps it takes on average.
When you roll a die, an even number comes up in 3 of the 6 cases, so its chance is 3 / 6 = 1 / 2. When every case is equally likely like this, the number of cases you want divided by the total number of cases is called the probability. 0 means it never happens, and 1 means it always happens.
Rolling two dice gives 6 × 6 = 36 cases by the rule of product.
The probability that both dice show 6 is 1 in 36, so 1 / 36, which equals 1 / 6 × 1 / 6. That’s because the first die doesn’t change the chances of what the second die shows. Two such events are called independent, and the probability that independent events all happen is found by multiplying.
How many people do you need before the chance that two share a birthday passes 50%? Let’s assume every birthday is equally likely to be any of the 365 days.
The cases where at least one pair shares a birthday are many and hard to count. But “at least one pair matches” and “all different” always have exactly one of them happen, so their probabilities add up to 1. So we find the probability that all are different and subtract it from 1. The second person must be on a different day from the first, which is 364 / 365, and the third 363 / 365. Each birthday is independent, so we multiply them all.
With 23 people it already passes 50%. That’s because what counts is pairs, not people. 23 people make 23 × 22 / 2 = 253 pairs, and a single matching pair is enough. Random IDs work the same way: collisions come much sooner than the number of possible values suggests.
What do you get on average when you roll a die? Multiply each face by its probability and add them all up.
1 × 1/6 + 2 × 1/6 + 3 × 1/6 + 4 × 1/6 + 5 × 1/6 + 6 × 1/6 = 3.5
This value is called the expected value. No face shows 3.5, but the more you roll, the closer the average gets to it.
This tendency of the average to approach the expected value as the number of tries grows is called the law of large numbers. You can’t predict a single roll, but you can predict the average.
Linear search is the same. If the value is equally likely to be in any of the n slots, finding it in slot i takes i checks, so the expected value is the following.
On average, you find it after checking about half.
You roll a die once, then choose whether to keep the result as your score or roll once more. If you roll again, the second result is your score and you can't change it. If you choose so as to make the expected score as large as possible, what is that expected value? Answer with a decimal or a reduced fraction.