1.3.2 problem 26

(a)

The problem is isomorphic (having same structure) to the birthday problem. When sampling with replacement, each person corresponds to a date in the birthday problem, and the size of sample corresponds to the number of people in birthday problem. Hence, taking a random sample of $1000$ from a population of a million corresponds to asking a thousand people their birth date where there are a total of a million dates. Number of ways to take such a sample is $K^{1000}$ where $K$ is size of population. Similarly, number of ways to take sample without replacement corresponds to number of ways of having no birthday match in that situation: $K(K-1)\dots (K-1000+1)$

(b)

$$P\left(A\right)=1-P\left(A^c\right)=1-\frac{K(K-1)\dots (K-1000+1)}{K^{1000}}$$

where $K=1000000$.