For a positive integer $N$, let $[N] = \{1,\cdots,N\}$ and $\binom{[N]}{n}$ denotes the set of all $n$ sized subsets of $[N]$. Supose we want to pick $(n+1)$-sized sample of $[N]$ uniformly randomly (meaning every element of $\binom{[N]}{n+1}$ is sampled with equal probability). This can be clearly done by picking $n+1$ elements without replacement. This is equivalent to the follwing 2-staged random process
-
Sample an element of $\binom{[N]}{n}$ uniformly. Call this sample $X$.
-
Sample an element $i$ from $[N]\setminus X$
Then it can be shown that $Y=X\cup\{i\}$ is a uniform element of $\binom{[N]}{n+1}$, i.e. for a fixed $I\in \binom{[N]}{n+1}, Pr[Y=I] = \frac{1}{\binom{N}{n+1}}$.
Proof: Fix $I=\{i_1,\cdots, i_{n+1}\}$. Then $Pr[Y=I] = \sum_{j=1}^{n+1}Pr[i=i_j\mid X=I\setminus\{i_j\}]Pr[X=I\setminus\{i_j\}] = \frac{n+1}{N-n}\cdot \frac{1}{\binom{N}{n}} = \frac{1}{\binom{N}{n+1}}$
Similary If we sample $Y$ from $\binom{[N]}{n+1}$ and delete a uniform random element $i$ from $Y$, then $X=Y\setminus \{i\}$ is a uniform random element of $\binom{[N]}{n}$.
Proof: Fix $I\in \binom{[N]}{n}$. Then $Pr[X=I] = \sum_{j\in [N]\setminus I}Pr[i=j\mid Y = I\cup\{j\}]Pr[Y = I\cup\{j\}] = \frac{N-n}{n+1}\cdot \frac{1}{\binom{N}{n+1}} = \frac{1}{\binom{N}{n}}$
Now let $[N]^n$ denotes the set of all ordered $n$-tuples of $[N]$. In order to sample a uniform element of $[N]^{n+1}$, we first sample an uniform element $X$ of $[N]^n$ and then sample an uniform $i$ from $[N]$. Then $Y=(X,i)$ is a uniform element of $[N]^{n+1}$.
Proof: Fix $I=(I^-,i_{n+1})\in [N]^{n+1}$, where $I^-\in [N]^n$. Then $Pr[Y=I] = Pr[\{X=I^-\} \cap\{i=i_{n+1}\}] = Pr[i=i_{n+1}\mid X=I^-]Pr[X=I^-] = \frac{1}{N}\cdot \frac{1}{N^n} = \frac{1}{N^{n+1}}$.
Now my question: In order to generate a uniform sample from $[N]^n$, we generate a uniform $Y$ from $[N]^{n+1}$ and just discard the last entry. My proposed proof is following:
Proof: Fix $I \in [N]^n$. Then if $X=(Y,i)$, $Pr[Y=I]. = \sum_{j=1}^N Pr[Y=I\mid X=(I,j)]Pr[X=(I,j)]$. Now the term $Pr[Y=I\mid X=(I,j)] = 1$, because $I$ is already fixed. So the above expression is equal to $\frac{1}{N^n}$.
Is the last proof correct? My initial thought was that removing a random element from $Y$ would give the result, but I could not prove it. I think the first three proofs are correct. Correct me I am wrong.
The motivaion for this question is analysis of some random process, see for example Lemma 6 of Algorithms for lp Low-Rank Approximation. Without going into much detail, there is was shown a random element of $\binom{[N]}{2k}$ has some property. The way it was shown that first sampling an element of $\binom{[N]}{2k+1}$ and then removing a random elemet from the sample. I have seen such argument elsewhere also.