There are generally 9 "random" digits in a 16-digit Visa/MC card number.
The BIN/IIN is traditionally the first 6 digits. Extended BINs can be 8-11 digits, which is like subnetting -- the BIN sponsor can delegate assignment control of an extended BIN range to another entity. So in some cases, there can be as few as 4 "random" digits in the full card number (PAN).
E.g.:
BIN "random" Check
411111 111111111 1
ExtendedBIN "random" Check
41111111111 1111 1
If you were sweeping a PAN range for live numbers, you'd start with a known-valid BIN, probably 6 or 8 digits. Then randomly choose the next 9 (or 7) digits, and then calculate the check digit.
We can't know the likelihood of hitting a valid number without knowing the count of assigned PANs in that BIN, but clearly the capacity would be 1 billion (or 10 million) possibilities.