I am trying to solve the following problem. An integer is picked independently at random from the first n integers 1, 2, . . . , n, with replacement. What is the probability that in a sample of r successive draws the numbers are drawn in a non-decreasing sequence?
The difficulty arises because there could be repeats (eg 12233335 is a valid sequence) and we do not know how many distinct integers are drawn and how many repeats there might be. I considered calculating the probability that given the previous number, the next number would be at least it, using the law of total probability. But this only works for two adjacent elements, not the whole sequence. I also tried using a counting argument, but this is difficult because not only is the distinct integers we will choose not known, how many repeats there are is also not known.
How can this be approached?
For the non-decreasing part, the number of "good" selections are equivalent to putting $r$ tokens in $n$ boxes numbered $1$ through $n$ which automatically means a non-decreasing sequence
By stars and bars, this equals $\dbinom{r+n-1}{r}$
and $Pr = \dbinom{r+n-1}{r}\Big{/}n^r$
PS:
You could also look at this answer which is a similar problem couched in different garb.