Suppose that I begin to draw $N$ cards randomly from a deck of $N$ cards (every card has written a number from $1$ to $N$ in its surface) and when the j written card is in the j-th draw I take it out from the deck. When I have drawn all cards I count how many are still in my hand and then I write in every card a new number so it will be in their surfaces from 1 to how many I still have and then replay the procedure for the remaining cards.
Every loop of the procedure ends when I have drawn and then check all of the cards in my hand. Let $X_n$ be the number of the cards that are still in my hand after n loops and $$S=\inf{\{k>0:X_k=0\}}$$ Show that $M_n=X_{\min{\{S,n\}}} + \min{\{S,n\}}$ is a martingale.
An example for $N=33$
- $3$ are drawn correctly, $n=1$: $M_1=30+1$
- $5$ are drawn correctly, $n=2$: $M_2=25+2$
- $1$ are drawn correctly, $n=3$: $M_3=24+3$
...
for $j\geq k$ (let $S=k$, the stopping time): $M_j=k$
Is $E[X_{\min\{S,n+1\}}\mid F_n]=X_{\min\{S,n\}}-E(Y_{n+1})$ where $Y_{n+1}$ is the correct - matching draws from the $X_{\min\{S,n\}}$ (if I have reach the stopping time I draw $0$ from $0$), correct and if it is how can I work with $E\left[{\min\{S,n+1\}}\mid F_n\right]$?
Thanks in advance
Let's post an answer, solving the hat problem (in comment) which is actually the same.
Let $Y_n$ be the correct draws of the remaining hats in the n-th loop.
We can see that $E(Y_n)=E(Z_1+\dots+Z_{X_n})$ where $Z_i=1$ if the i-st person gets his hat, or $Z_i=0$ if not. We can proove that $E(Z_i)=\frac{1}{X_n}$, one proof is that $Z_1,\dots,Z_n$ are exchangeable random variables, or we can see that $E(Z_k)=1\cdot\frac{X_n-1}{X_n}\frac{X_n-2}{X_n-1} \dots \frac{1}{X_n-k+1}$, so $E(Y_n)=1$ .
Now back to the main question,by taking cases for $X_n <T $ or not, we can find that if $X_n \geq S$ then $E(M_{n+1})=S$ and that if $X_n <S$ then $E(M_{n+1})=X_n -E(Y_{n+1})+n+1=X_n+n$ and so $E(M_{n+1})=X_{min(n,S)}+min(n,S)$.