Recently, I had played a dice game with my classmates. The game is like that:
Find a person rolls a dice and got a number $X$, then he rolls it again. If he gets $X$ again, the game stops; if he gets another number $Y$, he rolls it again. He rolls the dice again and again until the number has appeared before.
Then, I thought of a question: What is the probability of rolling the dice with $F$ faces $N$ times and stop when he rolls again $\left(F\ge N>0\right)$? Let $P\left(X\right)$ be the probability of rolling the dice $X$ times and stop when he rolls again. Then, $$P\left(N\right)=\left(1-\dfrac{1}{F}\right)\left(1-\dfrac{2}{F}\right)\left(1-\dfrac{3}{F}\right)\cdots\left(1-\dfrac{N}{F}\right)\dfrac{N}{F}=\dfrac{N\left(F!\right)}{F^{N+1}\left(F-N-1\right)!}$$
Obviously, $P\left(1\right)+P\left(2\right)+\cdots+P\left(F\right)=1$. You can prove it by the probability. However, I want to find an algebraic way to solve it. but it is hard because of the complicated expression. Is there any ways can I solve it? Also, I want to find the expected value of $P\left(N\right)$, which means I need to find the sum $\sum_{k=0}^F kP\left(k\right)$. Is there any closed form? Please answer. Thank you!
Here is what i would do to model the situation. Since typing matrices with dots is a problem for me, i will type matrices in the special case $F=7$, seven faces. The game is modeled by the Markov chain with states $\boxed 0,1,2,3,4,5,6,7$. Here $0$ is "final", absorbant, a no escape state. All other states $k$ have the meaning of "already $k$ different face numbers were seen", and the game starts after the first rolling and seeing the first number, so $1$ is initial. The picture of the states is:
$\require{AMScd}$ \begin{CD} 1 @>{1-\frac17}>> 2 @>{1-\frac27}>> 3 @>{1-\frac37}>> 4 @>{1-\frac47}>> 5 @>{1-\frac57}>> 6 @>{1-\frac67}>> 7 \\ @V {\frac 17} V V @V {\frac 27} V V @V {\frac 37} V V @V {\frac 47} V V @V {\frac 57} V V @V {\frac 67} V V @V {\frac 77} V V \\ 0 @= 0 @= 0 @= 0 @= 0 @= 0 @= 0 @>1>> 0 \end{CD}
The transition matrix is $$ \begin{aligned} A &= \begin{bmatrix} 1& \\ \frac 17 & 0 & \frac 67 \\ \frac 27 & & 0 & \frac 57 \\ \frac 37 & & & 0 & \frac 47 \\ \frac 47 & & & & 0 & \frac 37 \\ \frac 57 & & & & & 0 & \frac 27 \\ \frac 67 & & & & & & 0 & \frac 17 \\ \frac 77 & & & & & & & 0 \end{bmatrix} = T \underbrace{ \begin{bmatrix} 1& \\ & 0 & 1 \\ & & 0 & 1 \\ & & & 0 & 1 \\ & & & & 0 & 1 \\ & & & & & 0 & 1 \\ & & & & & & 0 & 1 \\ & & & & & & & 0 \end{bmatrix} }_{=:\Lambda\text{ Jordan matrix to eigenvalues }1;0,0,\dots,0} T^{-1} \ ,\\[3mm] &\qquad\text{ where the base change matrix is} \\ T&= \begin{bmatrix} 1\\ 1&\frac{6!}{7^6}\\ 1&&\frac{5!}{7^5}\\ 1&&&\frac{4!}{7^4}\\ 1&&&&\frac{3!}{7^3}\\ 1&&&&&\frac{2!}{7^2}\\ 1&&&&&&\frac{1!}{7^1}\\ 1&&&&&&&\frac{0!}{7^0}\\ \end{bmatrix} = \begin{bmatrix} 1\\ 1&t_1\\ 1&&t_2\\ 1&&&t_3\\ 1&&&&t_4\\ 1&&&&&t_5\\ 1&&&&&&t_6\\ 1&&&&&&&t_7\\ \end{bmatrix} \ . \end{aligned} $$ The labels for the rows and columns are $0,1,2,\dots,F$. Above $F=7$, but please write in mind the general matrices instead.
The diagonal entry $t_k$ in $T$, $1\le k\le F$, is $$ \color{blue}{t_k=\frac{(F-k)!}{F^{F-k}}}\ .$$
The inverse of $T$, the matrix $T^{-1}$, has the same positions for non-zero elements as $T$, diagonally we have the inverse values, and the first column is $1;-1/t_1,-1/t_2,\dots,-1/t_F$.
Let $p(k)$ be the probability to follow the path $1\to 2\dots\to k\to 0$. In words, last (non-final) state is $k$ and/or we reach the final state after exactly $k$ steps.
Then the entry in the position $(1,0)$ of $A^k$ is the probability to reach the final state in at most $k$ steps. So to get exactly $k$ steps we look at the $(1.0)$ entry of $(A^k-A^{k-1})$.
So the probabilities $$ \begin{aligned} p(1) &= \frac 1F\ ,\\ p(2) &= \left(1-\frac 1F\right)\frac 2F\ ,\\ p(3) &= \left(1-\frac 1F\right)\left(1-\frac 2F\right)\frac 3F\ ,\\ &\vdots\vdots\vdots\vdots\vdots\\ &\vdots\vdots\vdots\vdots\vdots \text{ and so on till}\\ &\vdots\vdots\vdots\vdots\vdots\\ p(F-1) &= \left(1-\frac 1F\right) \left(1-\frac 2F\right) \dots \left(1-\frac {F-2}F\right) \frac {F-1}F \ ,\\ p(F) &= \left(1-\frac 1F\right) \left(1-\frac 2F\right) \dots \left(1-\frac {F-2}F\right) \left(1-\frac {F-1}F\right)\frac FF \ , \end{aligned} $$ (written here explicitly, please compare with the posted formulas,) can be also obtained by building $\Lambda^k-\Lambda^{k-1}$, followed by conjugation with $T$ to obtain $T(\Lambda^k-\Lambda^{k-1})T^{-1}$, followed by looking into the $(1,0)$ entry. Doing this, we obtain for $p(k)$ the product of the row vector with entries $0;0,\dots,0,-t_k,t_k,0,\dots$ (with $-t_k$ in the column with label $k$, and $t_k$ in the column with label $(k+1)$, if this column still exists), and the column vector with entries $1;-1/t_1, -1/t_2, \dots$, i.e
This is not so important per se. (Since we already know a simple formula for $p(k)$.) But we can use it, or equivalently the Jordan decomposition (and type more, but type structurally) to compute the sum $$ \begin{aligned} \sum_{1\le k\le F}k\; p(k) &= p(1)+2p(2)+\dots+Fp(F) \\ &=\text{Entry $(1,0)$ in }T\Big(\ (\Lambda^1-\Lambda^0) +2(\Lambda^2-\Lambda^1) +3(\Lambda^3-\Lambda^2)+\dots +F(\Lambda^F-\Lambda^{F-1})\ \Big)T^{-1} \\ &=\text{Entry $(1,0)$ in } T \begin{bmatrix} 0\\ 0 & -1 &-1 & -1 &\dots & -1\\ 0 & &-1 & -1 &\dots & -1\\ 0 & & & -1 &\dots & -1\\ \vdots & & & &\ddots &\vdots\\ 0 & & & & & -1 \end{bmatrix} T^{-1} \\ &=\text{Entry $(1,0)$ in } \begin{bmatrix} 0\\ 0 & -t_1 &-t_1 & -t_1 &\dots & -t_1\\ 0 & &-t_2 & -t_2 &\dots & -t_2\\ 0 & & & -t_3 &\dots & -t_3\\ \vdots & & & &\ddots &\vdots\\ 0 & & & & & -t_F \end{bmatrix} \begin{bmatrix} 1 &\\ -1/t_1 &1/t_1\\ -1/t_2 &&1/t_2\\ -1/t_3 &&&1/t_3\\ \vdots & & & &\ddots \\ -1/t_F &&&&&1/t_F\\ \end{bmatrix} \\ &=t_1\left(\frac 1{t_1}+\frac 1{t_2}+\frac 1{t_3}+\dots+\frac 1{t_F}\right)\ . \end{aligned} $$ In our special case the above is: $$ \begin{aligned} p(1)+2p(2)+\dots+7p(7) &=\frac {6!}{7^6} \left( \frac1{0!}{7^0} + \frac1{1!}{7^1} + \frac1{2!}{7^2} + \frac1{3!}{7^3} + \frac1{4!}{7^4} + \frac1{5!}{7^5} + \frac1{6!}{7^6} \right) \\ &=\frac{355081}{117649} \approx 3.0181387007114\dots\ . \end{aligned} $$ Because in the parenthesis the sum is a "special cut" of the exponential series, i am not expecting a closed formula.
Computer check:
Some further check / experiment: