secp256k1 point density
I  also know that the curve order is $q$, with $q&lt;p$. That means there exist $q$ valid points on the curve,


True


  which is less than all the values that $x$ could have in $\mathbb{Z}_p$


Actually, that's less relevant than you think.


For every $x$ value in $\mathbb{Z}_p$ that has a valid solution, there are two values of $y$ that satisfy the equation (and hence correspond to two points).  It's easy to see, if $(x, y)$ is a solution, then so is $(x, -y)$ (aka $(x, p-y)$)


Note: some elliptic curve have 1 or 3 $x$ values that correspond to a single $y$ value (which is the $y$ value 0) - secp256k1 is not one of those curves.

In addition, there is a single 'point of infinity' which doesn't correspond to a solution to the equation, but is thrown in as an additional group element.

Hence, there are exactly $(q-1)/2$ $x$ values that correspond to (at least one) valid point.  Since $p \approx. q$, this if you pick an $x$ value at random, you have almost exactly a 50% probability of picking one with a solution.