Ok. Here's a question I just read in a book relating to combinatorics and probability. I'm not able to make head and tail about how I should approach it, so here goes:
You have a device that generates random numbers less than or equal to an integer i. The device has generated x random numbers yet. Compute the probability that the next number it generates, is a repetition.
For example, when i equals 2, and x equal 2, the answer is 50%, as in second move, the device may generate 1 or 2, which was generated previously as well.
So, I tried to think of it as a problem with probability being multiplied in case 1, to those in case 2, and so on, but that doesnt seem to be correct. Similarly, use of sets doesnt yield any merrier results. I'm just utterly confused how I should proceed, the book doesnt even have answers for this odd-numbered question, so stuck between a hard place and a rock. Any pointers to the solution, or entire solutions themselves, would be respected and appreciated.
Thanks in advance!
What we are looking for is $$\sum_{k=1}^x P(k,x)\cdot\frac{k}{i}$$ where $P(k,x)$ is the probability that exactly $k$ numbers have come up in $x$ moves so far.
For example, if two numbers (say, three and five) have come up in five rolls of a die, the results will look like: $$\begin{array}{c|ccccc}3&\times&\times&&&\times\\\hline5&&&\times&\times\end{array}$$
There are $\binom{i}{k}$ ways to choose the list of numbers that come up.
Then, there are ${x\brace k}k!$ ways to arrange the $\times$ marks.
[${a\brace b}$ is a Stirling number of the second kind.]
Finally, the probability of any given arrangement is $i^{-x}$.
Thus the answer is $$\sum_{k=1}^x\binom{i}{k}{x\brace k}k!\ i^{-x}\ \frac{k}{i}$$ which you can simplify to some extent.
For example, after four throws of a six-sided die, the chance the fifth throw will produce a number you've already seen is $$\frac1{1296}+\frac{35}{648}+\frac5{18}+\frac5{27}=\frac{671}{1296}\approx51.77\%$$