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?

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.
