0
$\begingroup$

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!

$\endgroup$
3
  • $\begingroup$ Seems like a conditional probability problem. Let X(1)= X_1, X(2)=X_2 be the first two outcomes. Then, what is P(X(3)=X_1 or X(3)=X_2 | X(1)=X_1 and X(2)=X_2) ). The notation may be wrong, but I think the idea is "spiritually correct". $\endgroup$
    – gary
    Mar 25, 2015 at 7:25
  • $\begingroup$ "You have a device that generates random numbers less than or equal to an integer i." Does this sentence define the distribution of the random numbers being generated? (Are they independent? What is the probility of rnd=-111 if i=2? $\endgroup$
    – zoli
    Mar 25, 2015 at 7:41
  • $\begingroup$ The example seems to suggest that the machine is producing positive integers with uniform distribution. But if the answer is 50%, then x=1. $\endgroup$ Mar 25, 2015 at 7:47

1 Answer 1

0
$\begingroup$

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\%$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .