Take the 2-minute tour ×
Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

Let's assume I have a (one-dimensional) array $I$ with a finite number $N$ elements. I also have a function $A$ that maps each element $I_n$ (for $0\leq\ n \lt N$) to the corresponding element $O_n$ in array $O$.

I also have a second function $B$ that maps each element $I_n$ (for $0\leq\ n \lt N$) to the corresponding element $O'_n$ in array $O'$.

If $O = O'$ (that is for $0\leq\ n \lt N$, for each $I_n$ in $I$, $O_n = O'_n$), I can say $A$ and $B$ are functionally equivalent across the domain $0\leq\ n \lt N$). However, if there exists at least one element $I_n$ such that $O_n \ne O'_n$, then I know $A$ and $B$ are not functionally equivalent.

Assume that I know $m$ elements in $O'$ and I know all $N$ elements in $O$. For the elements I know, if even one element $O'_n \ne O_n$, then I can say with certainty that $A$ and $B$ are not functionally equivalent. However, given that for all $m$ number of known elements in $O'$, $O'_n = O_n$, is it mathematically possible to determine the probability $P$ ($0 \leq\ P \leq 1$) that $A$ is functionally equivalent to $B$?

For example, if $N = 500$ and $m = 500$, and for each $I_n$, $O_n = O'_n$, then I can say with a certainty $P = 1$ that $A$ and $B$ are functionally equivalent across that domain. However, can I determine $P$ if $m = 400$, or if $m = 300$? Intuitively $P$ should be greater for $m = 400$ than for $m = 300$, but can I quantify that difference?

Essentially my problem is that I have two black boxes $A$ and $B$, I know all the outputs of $A$ but I do not know all the outputs of $B$, and $B$ is very computationally expensive to use. As a result, I do not want to test every input with $B$, and I'm willing to accept some chance of error by testing only a subset of inputs-- but can I quantify that chance of error?

share|improve this question
There is no information in this question that even suggests a probability model for the two functions, so the short answer is no, you cannot determine a probability. –  whuber Jan 9 '13 at 14:49
add comment

1 Answer 1

up vote 3 down vote accepted

Think of your series of tests as a sequence of trials, each of which takes a values on the set $\{0,1\}$. Let $x_n$ be a random variable describing the outcome of the test of input $n$: $x_n$ = 1 if $O_n = O^{\prime}_n$, and $x_n=0$ otherwise. You want to compute $\Pr[x_1 = \cdots = x_N = 1 \mid x_1 = \cdots x_m = 1]$, where $1 \leq m \leq N$.

It does not appear from your description that you have any prior information indicating that some of the inputs are more likely to generate matches than any of the other inputs. Nor does it sound like the inputs are grouped into subsets on which the $x_n$ exhibit statistical dependence such that, e.g., $\Pr[x_i=0 \mid x_j = 0] \neq \Pr[x_i = 0]$ for some $i,j$. If both these conditions hold, then you may treat the sequence $x_1, x_2, \ldots$ as a sequence of independent random variables drawn from the same Bernoulli distribution. Let $\theta \in [0,1]$ denote the Bernoulli parameter for this distribution: for all $n$, $\Pr[x_n=1]=\theta$.

Since the random variables $x_1, x_2, \ldots $ are independent and identically distributed, they are automatically exchangeable. We may then define for each $m$ a random variable $X_m = \sum_{n=1}^m x_n$, and are assured that the probability distribution over $X_m$ depends only on $m$, and not on the order in which the $x_n$'s are sampled. Likewise we may define $P_m = \Pr[X_N = N \mid X_m=m]$, which is what you want to know.

This problem lends itself well to a Bayesian approach, in which we treat $\theta$ as being itself a random variable that takes values on the unit interval. We'll use the fact that $X_m=m$ to estimate a probability distribution over $\theta$, and then use that distribution to estimate the probability that $X_N=N$.

For each $n$, $X_n$ takes a binomial distribution with probability mass function

$f(k \mid \theta) = \Pr[X_n = k \mid \theta] = {n \choose k}\, \theta^k (1-\theta)^{n-k}$

where $k \in \{0,1, \ldots, n\}$. Using Bayes' Theorem,

$f_n(\theta \mid k) = f_n(k \mid \theta)\cdot f(\theta) \, / \, \sum_j f_n(j \mid \theta)$

where $j = 0, 1, \ldots, n$.

Here $f(\theta)$ represents your prior beliefs about the likely values of $\theta$, which you hold before performing your first test. It might be that you have no prior beliefs about how likely it is that any given test will yield a match, in which case you would represent your beliefs with a uniform distribution: $f(\theta)=1$.

However, based on the background you provide, it seems likely that you do in fact have prior beliefs, perhaps rather strong beliefs, that the tests "should work." Put it this way: if your first three tests were all failures, would you be very surprised? If you held truly uninformative priors, then you should not be.

Look, I gotta run, so I'll just summarize the rest of the recipe, without further justification or comment:

Represent $f(\theta)$ with a Beta distribution. Set the two parameters of the Beta distribution to roughly represent your prior beliefs -- maybe $a=5$ and $b=1$.

Use Bayes' Theorem together with the formula for the binomial distribution to compute the posterior distribution $f_m(\theta \mid k=m)$ of $\theta$. This will be a Beta distribution with paramaters that depend on $a, b$ and $m$.

For a given fixed value of $\theta$, $P_{m|\theta}$ is the probability that the next $N-m$ trials would all have been successes, were they to be conducted:

$P_{m|\theta} = \theta^{N-m}$

Compute $P_m$ by integrating $P_{m|\theta}$ over the posterior distribution:

$P_m = \int_0^1 \theta^{N-m} f_m(\theta \mid k=m) d\theta$ .

That's your answer.

Additional thought: Can you quantify the costs of error versus the costs of testing? If so, then you can optimize your choice of $m$ to minimize total costs in expectation, using Bellman's Principle of Optimality. Let $C$ denote your cost of error and $c$ the cost per test. Your stopping rule is: keep conducting tests until either you hit a failure or the cost of testing exceeds the marginal expected value of the next test.

Let $V_m$ denote the total expected costs of continuing testing until you reach an optimal stopping point, conditioned on having already conducted $m$ tests and having not yet had a failure. Suppose at that point you ponder conducting one more test. If you do the test, you incur a cost $c$. With probability $1-\theta$ your next test would be a failure, which is actually good: you avoid the cost of conducting more tests, as well as the cost of error. With probability $\theta$, the test is a success, and you've reduced your expected costs of continuing the testing program, from $V_m$ to $V_{m+1}$: also good. Hence your expected net benefit of continuing to test are given by the expected reduction in "continuation costs", less the cost of the test itself. If you stop, you accept the expected cost of error $(1-P_m) C$. So:

If (STOP): total future expected costs are: $(1-P_m) C$.

If (KEEP TESTING): total expected future costs are: c + $\theta V_{m+1}$.

Optimal choice: STOP at stage $m$ if and only if $(1-P_m) C \leq c + \theta V_{m+1}$.


$ V_m = \min \{(1-P_m) C, c + \theta V_{m+1} \}$.

The above defines implicitly a recursive formula for computing $V_m$ given $V_{m+1}$. Using the boundary condition $V_N=0$ one may then solve for $V_m$. Apply the stopping rule.

share|improve this answer
This is awesome, I cannot thank you enough! My one upvote feels so puny. Optimizing m was my next step if it was in fact possible to do, so thanks for the additional guidance on that as well. –  Andrew Jan 9 '13 at 18:24
You are most welcome. –  Arthur Small Jan 9 '13 at 18:25
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.