Random matches in $2$ arrays (Sedgewick Algorithms $1.1.39$) Write a Binary Search client that takes an int value $T$ as command-line argument and runs $T$ trials of the following experiment for $N = 10^3, 10^4,
10^5,$ and $10^6$ : generate two arrays of $N$ randomly generated positive six-digit int values.
Find the number of values that appear in both arrays. Print a table giving the average value of this quantity over the $T$ trials for each value of $N$.  
Here Sedgewick suggests empirical study of this problem, but is there analytical solution for this?
Results (for $100$ trials):
$$
\begin{array}{|c|c|}
\hline
10ˆ3 & 0.00 \\ \hline
10ˆ4 & 0.02 \\ \hline
10ˆ5 & 0.10 \\ \hline
10ˆ6 & 1.14 \\ \hline
\end{array}
$$
 A: Let us consider a more general version, in which the arrays have length $N$, and their values are taken from a domain of size $M$ (in your case, $M=10^6$). Let us denote the two arrays by $A,B$.
There are several possible interpretations of the phrase the number of values that appear in both arrays. You seem to be counting the number of indices $i$ such that $A_i = B_i$. It is easy to calculate the expected number of such indices: it is $N/M$.
Another interpretation is: the number of values in $[M]$ that appear in both $A$ and $B$. In other words, the size of the intersection of $A$ and $B$, considered as sets. Here the expectation takes a bit longer to calculate.
For $i,j \in [N]$, let $E_{ij}$ denote the event "$A_i \neq A_{i-1},\ldots,A_1$, $B_j \neq B_{j-1},\ldots,B_1$, and $A_i = B_j$". The expected number of common values is $\sum_{i,j=1}^n \Pr[E_{ij}]$. We can calculate
$$
\Pr[E_{ij}] = \frac{1}{M} \left(1 - \frac{1}{M}\right)^{i+j-2}.
$$
Therefore the expected number of common values is
$$
\frac{1}{M} \sum_{i,j=0}^{N-1} \left(1 - \frac{1}{M}\right)^{i+j} =
\frac{1}{M} \left(\sum_{i=0}^{N-1} \left(1 - \frac{1}{M}\right)^i\right)^2 =
\frac{1}{M} \left(\frac{1 - \left(1-\frac{1}{M}\right)^N}{\frac{1}{M}}\right)^2.
$$
If $N \ll \sqrt{M}$ then $(1-\frac{1}{M})^N \approx 1-\frac{N}{M}$, and so the expected number of common values is roughly
$$
\frac{N^2}{M}.
$$
For large $M$ and arbitrary $N$, the expected number of common values is roughly
$$
(1-e^{-N/M})^2 M.
$$
