Suppose you are walking around a circular path made up of $n$ tiles.
Each tile $i$ is assigned a distinct value $r_i$ by a random variable uniformly distributed on the set of integers $\{1,...,k\}$ for some fixed $k$ with $1 \le k \lt n$.
You start on a random tile with all tiles equally possible as starting points.
You move in the following manner:
- From the start tile $s$ you move $r_s$ steps clockwise to some tile $t$.
- From any other tile $t$ you move $r_t$ steps clockwise to some tile $u$.
- You continue to move in this fashion until you reach a tile which you have previously been to.
- From then on you will move in a loop and only move to tiles which you have previously been to.
Example:
Here we set $n=6$ so there are $6$ tiles and set $k=3$ (although it is possible that $k$ could be $4$ or even $5$ in this example).
We assign each tile a random value between $1$ and $k$ and randomly begin on the tile assigned $1$.
After making 4 moves we hit a tile we have already hit (the first value $2$ that we hit) and the moves now loop between the three tiles with the value $2$.
Now let $P_{n,k}$ be the probability in terms of $n$ and $k$ that you hit every tile.
When $k=1$:
All tiles will be assigned the value $1$ so you will always step around every tile before you return to you starting point. So $P_{n,1}=1$ for all $n$.
When $k=n-1$:
You could move to any other tile on you next turn.
Suppose you didn't want to move to a tile you already visited:
On your first turn you could move to any tile.
On your second turn you could move to any apart from the one you started on.
On your third turn you could move to any apart from the first two tiles you visited.
Inductively it follows that $P_{n,(n-1)}=1\times\frac{n-2}{n-1}\times\frac{n-3}{n-1}...\times\frac{1}{n-1}=\frac{(n-2)!}{(n-1)^{n-2}}$ for all $n$.
What is the general formula for $P_{n,k}$?