**Question:** In the match problem of Example 2.31 involving n, n > 1, individuals, find the conditional expected number of matches given that the first person did not have a match.

**Analytical Solution:** As we see from the the problem’s description, 2.31 has been reiterated with a condition. This can be solved by applying the method of the conditional expectations

E[X] = E[E[X|X=x]]

⇒ E[X] = E[X|X_{1}=0] P{X_{1}=0} + E[X|X_{1}=1] P{X_{1}=1}

- E[X] = 1 (from problem 2.31)
- E[X|X
_{1}=0] is an unknown - P{X
_{1}=0} = 1-P{X_{1}≠1} = 1 –^{1}⁄_{n}=^{n-1}⁄_{n} - E[X|X
_{1}=1]- Since the first one is a match and there are n-1 left, the probability of match of each of them is
^{1}⁄_{n-1} - The expected number of matches from the set of n-1 would be then equal to one
- Since the first one is already a match, the quantity E[X|X
_{1}=1] = 1 + 1 = 2

- Since the first one is a match and there are n-1 left, the probability of match of each of them is
- P{X
_{1}=1} =^{1}⁄_{n}(from problem 2.31)

Plugging these in the equality above, we get E[X|X_{1}=0] = ^{n-2}⁄_{n-1}

Observations:

- There is one significant change of the expected value as compared to scenario 2.31
- In 2.31, the expected value was a constant
- With a condition that the first one is not a match, the probability has become a function of the number of items (or hats)
- This would give us a variable number of hats to make additional observations in the simulation (which is the next section)

**Simulations **The simulations have been summarized in the chart below. What is being shown in the chart?

- Each bar has 1000 points
- each point is mean value of the number of matches for i iterations

- The number of iterations per point can be seen as a number below the bar
- Reading the first bar as an example
- It has number 10 written below it
- This means that each point is the average of 10 values
- Each value is the count of number of matches in a set of alphabets and it has been made sure that that first element is not a match (which is a requirement from the problem statement)

- Horizontal Bar: If you look closely there is a horizontal bar shown in the chart. This has been kept at 0.96
- Why 0.96? Since the alphabet, has 26 letters, the expected value from theory is
^{26-2}⁄_{26-1 }= 0.96

- Why 0.96? Since the alphabet, has 26 letters, the expected value from theory is

*Generalized Algorithm:* In the above example, we have looked at a system with a fixed number of units (hats). I have generalized the “Alphabet” algorithm from previous section to accommodate any list. I used the function to pass lists of increasing lengths and to see how the expected value changes, since, E[X|X_{1}=0] varies with n as ^{n-2}⁄_{n-1 }. This particular simulation took ~30 minutes for completion.

Reading the Chart: The chart has seven distributions shown and we can read it as follows. Each bar contains 1000 points and each point is a mean value generated from a 1000 selections of varying lengths. The length of the list can be seen from the label at the bottom of each of bar

*for example:*The first bar contains a 1000 points and each one of the 1000 points is a mean number of matches from a 1000 selections of length 10. The number 10 can be found at the bottom of the chart as a label- Also there are 7 horizontal lines showing the theoretical expectations
- As n becomes infinity, theoretically the expectation value becomes 1. This seems to be the case from the simulation too.

Comparing with theory. We know that E[X|X_{1}=0] varies with n as ^{n-2}⁄_{n-1 }. We can plot this simply as a function to see the behavior of E[X|X_{1}=0] with n. The plot has been done for lengths of lists from 3 to 25.

**Code**

The code is arranged in sequence for each of the charts

——————————————–

——————————————–

End of the post 😉

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.