What is the probability of selecting an item of a list of items that have not been selected before? Story behind my question
From time to time, I like to play DotA. It is a competitive computer game, where you pick 1 out of more than 100 heroes and play against each other. For simplicity, let's stick to 3 heroes.
For to learn how to play with every single hero, I like to pick one randomly at the start of every game. Playing with my friends, I was criticized for playing with heroes that I do not know.
The question
So I asked myself: What is the probability of getting a hero that I have not played before after $x$ games (and, as a consequence, encounter higher difficulty)?
Small example
Before the first game ($x=0$), the probability is $100$%. Then it gets difficult. Consider the following list of three heroes: $H = \{A, B, C\}$. Playing two games, these outcomes might occur:
$E = \{$$AA$, $AB$, $BA$, $BB$, $AC$, $CA$, $CC$, $BC$, $CB$ $\}$
In the following cases the probability of a new hero in the third game is $1/3$
$AB, BA, CB, BC, AC, CA$
In the following cases the probability of a new hero in the third game is $2/3$
$AA, BB, CC$
For example, after $AA$ the heroes $B$ and $C$ will still be new. In contrast, after seeing $BC$ only $A$ would be new.
My approach


*

*The probability of getting a new hero depends on the number of rounds played and the number of heroes available.

*There are 3 heroes in the easy example, in reality more than 100.

*Every hero has the same chance of being picked each game. So it could be the same for $x$ games in a row.
I think of it as a kind of binomial distribution. But it's not about "Prob. that a coin is head 5 out of 6 times". It's about the probability that anyone of those who have never been selected in games before is now selected.
How could one solve it?
 A: This is a nice example of something called a Markov chain. There is a lot of theory for Markov chains, if you'd like to learn about that sort of thing, but I'll try to give a short version here for your specific question.
A Markov chain is a system that moves from one state to another, and where the next state depends on the current state only. Another way of saying this is that all of the history of the system can be summarised in the current state, and that you don't have to remember the full history of how you got to that state in order to make predictions about future states.
In your case, you have a Markov system because after having played $n$ games, the only information you need to summarise the current state, is how many of the heroes you have picked before (how many are old heroes) and how many you have never picked before (how many are new heroes).
Markov chains are often represented either graphically or in matrix form. The graphical form is useful for understanding your problem better. The matrix form is useful for calculation properties of your system (like the probability of getting a new hero after having played $n$ games).
Here is a graphical representation for your system with the total number of heroes set to $h=4$.
$h=4$." />

*

*In the initial state, on the left, you have not picked any heroes and the probability of picking a new hero is $1$.

*Picking a new hero takes you to the next state, where the probability of picking an old hero is $\frac{1}{4}$ and the probability of picking a new hero is $\frac{3}{4}$.

*Picking an old hero means that you stay in the same state.

*Picking a new hero means that you move on to the next state.

*In the final state, you can always pick only old heroes and so you will stay there forever.

In matrix form, we represent the information like this. (I call this matrix $M_4$ to show that it is the Markov transition matrix for your system with $h=4$.)
$M_4 = \left[\begin{array}{ccccc}
0 & 0 & 0 & 0 & 0 \\
1 & \frac{1}{4} & 0 & 0 & 0 \\
0 & \frac{3}{4} & \frac{1}{2} & 0 & 0 \\
0 & 0 & \frac{1}{2} & \frac{3}{4} & 0 \\
0 & 0 & 0 & \frac{1}{4} & 1 \\
\end{array}\right]$
Here's why it is useful. If we represent the initial state with the probability vector
$$p_0 = [\ 1\ 0\ 0\ 0\ 0\ ] ^T$$
then we can find the state probability vector after $n$ games from $(M_4)^n \cdot p$. The state transition matrix tells you what the new probability distribution over states is after your next game.
A probability vector just means that the entries of the vector have to sum to $1$ and that each entry represents the probability of being in the state associated with that entry. So $p_0$ shows that at the beginning (after 0 games), the probability is $1$ that you are in the first state in the diagram. After the first two games
$$
\begin{align}
p_1 &= M_4 \cdot p_0 = [\ 0\ 1\ 0\ 0\ 0\ ] ^T \\
p_2 &= M_4 \cdot p_1 = (M_4)^2 \cdot p_0 = \left[\ 0\ \frac{1}{4}\ \frac{3}{4}\ 0\ 0\ \right] ^T
\end{align}
$$
This shows that

*

*you will always end up in the second state after the first game,

*there is a $\frac{1}{4}$ probability that you will stay in the second state after the second game, and

*there is a $\frac{3}{4}$ probability that you will move to the third state after the second game.

Your question was: What is the probability of getting a hero that I have not played before after $n$ games. We now split this into two parts

*

*What is the probability distribution over states after $n$ games – that is, what is $p_n$.

*What is the probability of getting a new hero, given $p_n$.

The second part is easy since the probability of picking a new hero in state $s$ is $\frac{h-s+1}{h}$, where $s\in\{1,2,\ldots,h+1\}$ is the index of the state and $h$ is the total number of heroes available. So, your final probability is
$$\sum_{s=1}^{h+1} \frac{h-s+1}{h} (p_n)_s$$
The first part is computed from $p_n = (M_h)^n\cdot p_0$. For this we need the general transition matrix for your problem, which is
$M_h = \left[\begin{array}{cccccc}
0 & & & & & \\
1 & \frac{1}{h} & & & & \\
& \frac{h-1}{h} & \frac{2}{h} & & & \\
& & \frac{h-2}{h} & \frac{3}{h} & & \\
& & & \ddots & \ddots & \\
& & & & \frac{1}{h} & 1 \\
\end{array}\right]$
A: I can only answer a related question. What you asked does not have a nice answer.
Suppose you have n heroes, I can answer: what is the distribution of number of games I need to play=m of them, where $m<n$
When you start, you played with 0 heroes, then, the chance you play with a new one is 1.
Then after you played with 1 hero, then the chance you play with a new hero is $(n-1)/n$… After you played with $k$, heroes, the chance you play with a new hero is $(n-k)/n$.
Now, the number of games you need to play with a new hero AFTER k heroes have been used is a geometric distribution with parameter $(n-k)/n$. (Notice it should be the geometric distribution starting at 1. On wikipedia, there is a geometric distribution starting at 0)
Let $X_1, X_2,… X_{n-1}$ be independently distributed as Geom$((n-1)/n)$, Geom$((n-2)/n)$,…, Geom$(1/n)$ respectively. The number of games it will take to play $m$ heroes is equal to
$1+X_1+…+X_{m-1}$
I guess what you are asking is $P(1+X_1+…+X_i=x+1, \text{for some } i)$
I don't think there is a closed form expression for this.
