please excuse (or change, if possible) the title if it doesn't make sense.
I have a problem which is something like this:
You have a variable $i$ which starts at $i=1$. You also have a target number of $j$, and you have an n-sided die (in my case $j=6$ and $n=6$ but ideally i'd like to be able to solve this generally.)
Now you repeatedly roll the n-sided die, each time the die the lands on a number greater than $i$ you increment $i$ by 1. This stops once $i=j$.
I've already calculated the mean number of rolls until $i=j$ as:
$$\sum_{x=n-(j-1)}^{n-1} \frac{n}{x}$$
Now i'd like to be able to produce a probability distribution of how many rolls until $i=j$. I'm currently only looking at $j=6$ and $n=6$ and have come up with a solution, however it is very manual.
I can model the probability of raising $i$ from 1 to 2 (assuming 6-sided die) in $x$ rolls as:
$$p_1(x)=\frac 16^{x-1}\times \frac 56 $$
Similarly the probability of raising $i$ from 2 to 3 in $x$ rolls
$$p_2(x)=\frac{2}{6}^{x-1}\times \frac 46 $$
(I'll skip the definition of $p_3(x)$ to $p_5(x)$)
Now for the probability of raising $i$ from 1 to 6 in just 5 rolls would be
$$p_1(1) \times p_2(1) \times ... \times p_5(1)$$
But what I need to do next is the probability of raising $i$ from 1 to 6 in 6 rolls, I realise I need to do something like:
$$p_1(2) \times p_2(1) \times ... \times p_5(1) + p_1(1) \times p_2(2) \times ... \times p_5(1) + ... \times p_4(1) \times p_5(2)$$
(Not sure if I removed too much from the above equation but essentially the sum of all the different products of $p_{1-5}$ where the arguments to the functions add up to 6, does that make sense?)
And then the above but for all arguments summing to 7 and on to Infinity.
So I'm wondering how to generalise this last step? It seems to be that it could/should be able to be represented as a function. Maybe there is something similar that already exists?
Thank you in advance. Let me know if i need to edit the question to clarify anything :)
Clearly you need $j \le n$
As Tony Hellmuth says in the comments, this is closely related to the Coupon Collector's problem. You can make the relationship even closer if you start with $i=0$, which has the effect of adding $1$ to the number of throws. Doing that, I believe you can say that the probability that the first time $i=j$ is the $r$th throw is $$ S_2(r-1,j-1) \frac{ n!}{(n-j)! n^r}$$ where $S_2(a,b)$ is a Stirling number of the second kind
For $n=j=6$ it gives probabilities like this table for varying $r$ starting at $i=0$ (if starting from $i=1$ then subtract $1$ from each $r$); in the tail $\mathbb P(R=r+1) \approx \frac56 \mathbb P(R=r)$. The expected value is $14.7$, median is $13$ and mode is $11$.