Probability of program equality based on samples Program p implements a side-effect-free function f that accepts k1 bytes as input and produces k2 bytes of output.
Suppose we take N samples (tuples of input/output pairs where p(i) = o), where the inputs are perfectly random. Program q satisfies these samples (q(i) = o).
Obviously, if N contains all input/output pairs, q = p. What is the probability that q = p, if the N is smaller, e.g. 10? What is the value of N to achieve 99.99% probability? Or 99.9999%? Is the domain size of the output important?
 A: Suppose there are $n$ possible inputs to the function.  In your case, assuming a byte can have $256$ values and the input consists of $k_1$ bytes, we have $n = 256^{k_1}$.  
The most difficult situation to detect is when only one of the inputs results in an error and all the other inputs are processed correctly.  In this case, the probability of finding the error on any one test is $1/n$.  If we perform $N$ tests, then the expected number of times we find the error case is $N/n$.  Assuming $N/n$ is small, the total number of error cases found will approximately follow a Poisson distribution with parameter $\lambda = N/n$, and the probability the error is not found in $N$ tests is $e^{-\lambda} = e^{-N/n}$.  If we want this probability to be small, say less than $0.0001$, then $e^{-N/n} < 0.0001$ requires $N > -n \ln(0.0001) \approx 9.21 n$.  
So to be $99.99\%$ sure with random testing that the error is detected requires a number of tests which is more than $9$ times the number of tests that would be required to test all possible inputs in a systematic, non-random, fashion.
A: I think what you are trying to do is that we take $N$ samples which may or may not be distinct samples from the $k_1$ input bytes. Let's name these $X_1, \dots , X_N$. Now as output we can have $2^{k_2}$ possible outputs. Note that not all outputs should have to be achievable. If we take the $N$ samples and they all have a different input, but the same output, this is not necessarily a problem. 
To be sure that $q=p$ we would be required to check all $2^{k_1}$ possible different inputs. 
If we do not assume a further structure on the input or output it is hard to answer your question of the probability that $q=p$. I am assuming that with $q=p$ you mean that for any input $i$ we have $p(i)=q(i)$. If you assume that any possible output of the $2^{k_2}$ is equally likely we would be looking at how many of the input samples we would need to guess correctly (perhaps independently) based on the size of the output space. Unless $k_1$ and $k_2$ are large and we have some more constraints I am sure that the level of certainty you require will correspond more to the probability of drawing $N$ different inputs then looking at anything else.
