probability of choosing $k$ linear independent elements from a finite field

Question

Let $\mathbb{F}_q$ denote a finite field with $q$ elements. What is the probability of choosing $k$ linear independet elements from $\mathbb{F}_q^n$?

I guess, it depends on how we choose from $\mathbb{F}_q^n$. If so, what's a considerable technique?

Answer 1

"I guess, it depends on how we choose..." Yes, that's true. From a linear algebraic perspective the most natural way is to divide the number of linearly independent ordered $k$-tuples of vectors from $\mathbb{F}_q^n$ by the total number of $k$-tuples. (In more probabilistic language: you choose with replacement, and the order of the choices does matter.) The latter number is easy: it's $(q^n)^k = q^{nk}$.

Do you want help computing the numerator? I would suggest you start with the cases $k =1$ and $k =2$ and employ the following technique: fill up your $k$-tuple one vector at a time. At each stage, count the number of ways you can add one more vector while maintaining linear independence. For instance, you have $q^n-1$ choices for the first vector because you can choose anything but $0$ to get a linearly independent $1$-tuple. For the second vector you don't want a scalar multiple of the first. There are $q$ scalar multiples of any nonzero vector in $\mathbb{F}_q^n$, so you have $q^n -q$ choices for the second vector. And so on...