order independence for sequences of dependent events

[MonDie]

I noticed a sort of probability problem in which different sequences of events have the same probability despite the events being dependent. I've proven an example below, but I still don't fully grasp why.

Here is the problem I use to demonstrate.
There is a bag of tubes. Testing for bad tubes, you test the tubes one at a time. Tubes aren't returned to the bag after testing, so there is one less tube each time (event dependence). Despite this, the probability of a good then a bad is equal to the probability of a bad then a good.

variables:
x = bad tubes / total tubes
y = 1 / total tubes.

derived:
If x is all the bad tubes, 1-x is all the good tubes.
y is 1 single tube.
1-y is total tubes with 1 tube gone.
x-y is the number of bad tubes with 1 bad tube gone.

Problem 1:

Probability that first is bad (x/1) and second is good ((1-y-(x-y))/(1-y)).
|
[math]\frac{x}{1}*\frac{1-y-(x-y)}{1-y}[/math]
|
[math]x*\frac{1-y-(x-y)}{1-y}[/math]
|
[math]x*\frac{1-x}{1-y}[/math]

Problem 2:

Probability that first is good ((1-x)/1) and second is bad (x/(1-y)).
|
[math]\frac{1-x}{1}*\frac{x}{1-y}[/math]

|

[math](1-x)*\frac{x}{1-y}[/math]

 

They're Equal

The equations from each problem give the same output with the same input values, so they're probably equal.
For example, when x=5/100 and y=1/100
.05*(.95/.99) = 0.047979798
.95*(.05/.99) = 0.047979798

Proof that they're equal.

[math]x*\frac{1-x}{1-y} = \frac{x(1-x)}{1-y} = (1-x)*\frac{x}{1-y}[/math]

---

Can one increase the line spacing between lines of math? I interspersed them with invisible white text. Edited June 8, 2014 by MonDie

[imatfaal]

Don't understand your variables and derivations. If y = 1/total it cannot be 1 (single tube) unless there is only one tube and even then I a queasy about the derivation.

 

If y= 1/total - say make total 10. y=1/10

1-y = 9/10

9/10 does not equal total number of tubes minus one.

If y = 1/total then

total = 1/y and total - 1 = (1/y) -1

 

 

And 1-x is not the number of good tubes - it is the proportion of good tubes

total = 10 bad = 7

x= 7/10

1-x = 1-7/10 = 3/10

[MonDie]

You're technically right. The first equation assumed 100 tubes total, with x as actual number of bad tubes.

 

You test the tubes one at a time. x is the number of bad tubes out of 100. Tubes are not replaced after removal.

Probability that first is bad and second is good.
[math]\frac{x}{100}*\frac{100-x}{99}[/math]

Probability that first is good and second is bad.
[math]\frac{100-x}{100}*\frac{x}{99}[/math]

 

To allow variation in tubes total, however, I needed to use proportions: either [math]\frac{x}{total}[/math], or [math]x = \frac{bad}{total}[/math]. The latter made the equations simple and readable.

Edited June 8, 2014 by MonDie

[John]

Let [math]n[/math] be the total number of tubes, and let [math]x[/math] be the number of bad tubes. Then there are [math]{n}\choose{x}[/math] possible arrangements of good and bad tubes.

 

The number of arrangements in which tube 1 is good and tube 2 is bad is [math]{n-2}\choose{x-1}[/math], as is the number of arrangements in which tube 1 is bad and tube 2 is good. Thus the probabilities are equal.

 

Essentially, if we consider our entire testing sequence to be a series of tubes ( ), then in either case we have one good tube and one bad tube in our first two slots, and so our remaining tube arrangements contain the same members, ordered in various ways.

 

Consider similar questions regarding the first three tests instead of the first two. Letting G be good and B be bad, the probabilities of GBB, BGB and BBG should be equal, whereas the probabilities of GGB and BBG should not (unless, of course, there are equal numbers of good and bad tubes).

[MonDie]

Let [math]n[/math] be the total number of tubes, and let [math]x[/math] be the number of bad tubes. Then there are [math]{n}\choose{x}[/math] possible arrangements of good and bad tubes.

 

The number of arrangements in which tube 1 is good and tube 2 is bad is [math]{n-2}\choose{x-1}[/math], as is the number of arrangements in which tube 1 is bad and tube 2 is good. Thus the probabilities are equal.

What kind of notation is this?

[John]

The notation is read "n choose x," and it denotes a combination.

 

Given n tubes, x of which are bad, there are n choose x ways to arrange the tubes in sequence. The symbolic definition is [math]{{n}\choose{x}} = \frac{n!}{x!(n-x)!}[/math].

Conceptually, here it means that given the n spots we have for our tubes, there are n choose x ways to choose x spots to hold the x bad tubes.

[imatfaal]

Lovely explanation John +1

[MonDie]

The hard part is noticing every instance in which a formula is applicable.

 

I'll look at it again in the morning.

Edited June 11, 2014 by MonDie

[MonDie]

John, that not only explains why they must be equal, but can easily be used to to construct a formula that solves for the probability of failing 1 of 2 tests. Before I get to that, I want to further clarify your reasoning by restating it in my own words.
In this instance, [math]{{n}\choose{x}}[/math] or alternatively [math]{{n}\choose{k}}[/math] is the number of ways to assign [math]k[/math] bad tubes within an [math]n[/math]-tuple of tubes. To calculate the probability of failing 1 of 2 tests with the two tests being performed on two members of the n-tuple, we need to calculate the number of variations on [math]{{n}\choose{k}}[/math] that assume 1 and only 1 of these members being assigned as a bad tube. This is easily calculated since there are two ways to fail 1 of 2 tests, and each way lends itself to [math]{{n-2}\choose{k-1}}[/math] permutations.

This is the formula derived from your concepts.

[math]2{{n-2}\choose{k-1}} \div {{n}\choose{k}}[/math]

We can broaden its applicability by making [math]t[/math] and [math]f[/math] the number of tests and failures, respectively.

[math]({{t}\choose{f}} \times {{n-t}\choose{k-f}}) \div {{n}\choose{k}}[/math]

---

[math]{{n}\choose{k}} = \frac{n!}{k!(n-k)!}[/math]

Below I have converted your variables to my variables, so I will be able relate my formula to yours.
Note that I've converted your [math]x[/math] to [math]k[/math] to avoid ambiguity.
INSERT: I gave up on comparing our formulae after realizing how complicated the task would be, as you're about to see.
|

yours to mine

[math]n = \frac{1}{y}[/math]

mine to yours

[math]y = \frac{1}{n}[/math]

|

yours to mine

[math]k = x \times n = \frac{x}{y}[/math]

mine to yours

[math]x = k \times y = \frac{k}{n}[/math]

To compare mine to yours, I will need to make my formula into a solution to the same problem. Presently my formula [math]\frac{x(1-x)}{1-y}[/math] only solves for the probability of one specific ordering of failures. I think I can make it into a solution using another formula I invented. The probability that neither A nor B occur when A and B are mutually exclusive, letting a=P(A) and b=P(B), is [math](1-a) \times \frac{1-b-a}{1-a}[/math]. In this instance, A should be the event of failing only the first of two tests, and B failing only the second of two tests.
Although this is looking like it will be a complicated solution, the alternative doesn't look much simpler.
|
[math]2{{n-2}\choose{k-1}} \div {{n}\choose{k}}[/math]
You found the secret message!
[math](2 \times \frac{(n-2)!}{(k-1)!((n-2)-(k-1))!}) \div \frac{n!}{k!(n-k)!}[/math]
Simplify
[math](2 \times \frac{(n-2)!}{(k-1)!(n-k-1)!}) \div \frac{n!}{k!(n-k)!}[/math]

Edited June 11, 2014 by MonDie

[John]

Well, keep in mind that the probability for either GB or BG in isolation is simply [math]\frac{{{n-2}\choose{k-1}}}{{{n}\choose{k}}}[/math]. There's no need to double it unless you're wanting to know the probability of either sequence happening.

 

As for simplification, factorials simplify in pleasant ways. Consider n! and (n - 1)! for instance. Now, n! is n(n - 1)(n - 2)...(2)(1) while (n - 1)! is (n - 1)(n - 2)(n - 3)...(2)(1), so for example (and assuming n > 0),

 

[math]\frac{n!}{(n-1)!} = \frac{n(n-1)(n-2)...(2)(1)}{(n-1)(n-2)(n-3)...(2)(1)} = n[/math].

 

Looking at our probability, then, we have

 

[math]\frac{{{n-2}\choose{k-1}}}{{{n}\choose{k}}} = \frac{\frac{(n-2)!}{(k-1)!((n-2)-(k-1))!}}{\frac{n!}{k!(n-k)!}} = \left(\frac{(n-2)!}{(k-1)!(n-k-1)!}\right) \left(\frac{k!(n-k)!}{n!}\right) = \frac{k(n-k)}{n(n-1)}[/math].

 

Don't worry too much about the combinatorics here. It's a handy way to look at certain (most?) discrete probability problems, but there's nothing wrong with the method you were using originally, once the appropriate variables are set up and the appropriate calculations carried out.

[MonDie]

That's good to know. I'm still trying to understand the last step of your simplification.

 

I realized that my formula for neither of two mutually exclusive events occurring [math](1-a) \times \frac{1-b-a}{1-a}[/math] simplifies easily.

[math]\frac{1-b-a}{1-a}[/math] is the probability that B hasn't occurred given that A hasn't occurred, but the whole thing simplifies to [math]1-b-a[/math].

I invented the formula trying to find the probability of a boardgame piece landing on a particular spot within the next x turns, a problem that didn't seem very intuitive at the time.

Edited June 12, 2014 by MonDie

[John]

Well, we can rearrange and expand, giving us the following (starting from the second-to-last step in my post above):

 

[math]\begin{array}{rcl} \left(\frac{(n-2)!}{(k-1)!(n-k-1)!}\right) \left(\frac{k!(n-k)!}{n!}\right) & = & \left(\frac{(n-2)!}{n!}\right) \left(\frac{k!}{(k-1)!}\right) \left(\frac{(n-k)!}{((n-k)-1)}\right) \\ & = & \left(\frac{(n-2)(n-3)...(2)(1)}{n(n-1)(n-2)(n-3)...(2)(1)}\right) \left(\frac{k(k-1)(k-2)...(2)(1)}{(k-1)(k-2)...(2)(1)}\right) \left(\frac{(n-k)(n-k-1)(n-k-2)...(2)(1)}{(n-k-1)(n-k-2)...(2)(1)}\right) \\ & = & \left(\frac{1}{n(n-1)}\right) \left(\frac{k}{1}\right) \left(\frac{n-k}{1}\right) \\ & = & \frac{k(n-k)}{n(n-1)} \end{array}[/math]

 

This last fraction also follows from the other method. Assume we're testing n tubes, and let k be the number of bad tubes. Then n - k is the number of good tubes.

 

The probability that the first tube is good is (n - k)/n, and in this case, what remains are k bad tubes and n - 1 tubes total, so the probability that the second tube is bad is k/(n - 1). Multiplying, we arrive at [math]\left(\frac{n-k}{n}\right) \left(\frac{k}{n-1}\right)[/math].

 

Now, the probability that the first tube is bad is k/n, and in this case, what remains are n - k good tubes and n - 1 total tubes, so multiplying, we arrive at [math]\left(\frac{k}{n}\right) \left(\frac{n-k}{n-1}\right)[/math].

[MonDie]

It's been so long since my last math course that I forgot how to multiply fractions.

[snipped]

This last fraction also follows from the other method. Assume we're testing n tubes, and let k be the number of bad tubes. Then n - k is the number of good tubes.

The probability that the first tube is good is (n - k)/n, and in this case, what remains are k bad tubes and n - 1 tubes total, so the probability that the second tube is bad is k/(n - 1). Multiplying, we arrive at [math]\left(\frac{n-k}{n}\right) \left(\frac{k}{n-1}\right)[/math].

Now, the probability that the first tube is bad is k/n, and in this case, what remains are n - k good tubes and n - 1 total tubes, so multiplying, we arrive at [math]\left(\frac{k}{n}\right) \left(\frac{n-k}{n-1}\right)[/math].

This made me realize that these problems are expressible as two multiplied series divided by a third series. I changed your n to m to avoid ambiguity within the series notation.

m = tubes total
k = tubes bad
g = good tubes drawn
b = bad tubes drawn

[math]\frac{(\sum_{n=0}^{b-1}k-n)*(\sum_{n=0}^{g-1}m-k-n)}{\sum_{n=0}^{b+g-1}m-n}[/math]

[math]\sum_{n=0}^{b-1}k-n[/math] The number of bad tubes (k) decreases by one each time a bad tube is pulled, which must be accounted for next time a bad tube is pulled. This will always be a numerator over the total number of tubes left unpulled.

[math]\sum_{n=0}^{g-1}m-k-n[/math] Similarly, the number of good tubes (m-k) decreases by one each time a good tube is pulled, which must be accounted for next time a good tube is pulled. This will always be a numerator over the total number of tubes left unpulled.

[math]\sum_{n=0}^{b+g-1}m-n[/math] Finally, the number of all tubes (m), your denominator, decreases by one each time any tube is pulled, which must be accounted for in the next pulling of a tube.

Edited June 16, 2014 by MonDie