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?

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.
