Probability of Signal getting through.

[dacruick]

Hi Everyone,

below I've attached an embarrassing drawing of a circuit with switches. Signal enters from the left side at both line. Given that each switch has a 50% chance of being open, what is the probability of signal reaching the end of the circuit(far right)?

The answer that I got was 45/128 but I have a feeling its wrong.

Cheers.

 

[berkeman]

Hi Everyone,

below I've attached an embarrassing drawing of a circuit with switches. Signal enters from the left side at both line. Given that each switch has a 50% chance of being open, what is the probability of signal reaching the end of the circuit(far right)?

The answer that I got was 45/128 but I have a feeling its wrong.

Cheers.

The probability is zero. The output is shorted. :tongue2:

 

[dacruick]

The probability is zero. The output is shorted. :tongue2:

I would have never caught your playful sarcasm without the little face.

 

[berkeman]

I would have never caught your playful sarcasm without the little face.

So if you un-short the output, can you show us how you got your answer? The vertical switches can short out the signal as well, right? So you need the right combination of shorts and opens for the differential signal to get through. Looks to me like the probability of the differential signal getting through is quite low...

 

[Mark44]

Maybe you already did this, but if not, what I would do is label the 8 switches (e.g., A, B, and C for the ones along the top, D and E for the ones that join the upper and lower branches, and F, G, and H for the ones along the bottom.

Determine all of the possible paths that the current could take.
ABC (p = 1/8)
ADGH (p = 1/16)
ADGEC (p = 1/32)
.
.
.
FGH (p = 1/8)

Once you get all of the possible paths from the upper left node, you can use symmetry to find the paths from the lower left node.
The overall probability should be the sum of the probabilities along the individual paths.

 

[berkeman]

Maybe you already did this, but if not, what I would do is label the 7 switches (e.g., A, B, and C for the ones along the top, D and E for the ones that join the upper and lower branches, and F, G, and H for the ones along the bottom.

Determine all of the possible paths that the current could take.
ABC (p = 1/8)
ADGH (p = 1/16)
ADGEC (p = 1/32)
.
.
.
FGH (p = 1/8)

Once you get all of the possible paths from the upper left node, you can use symmetry to find the paths from the lower left node.
The overall probability should be the sum of the probabilities along the individual paths.

Am I seeing the problem wrong? I'm seeing a differential signal being put in at the left, and wanting to see the differential signal at the right (after the OP unshorts it). So the series switches all need to be closed, and the parallel shorting switches all need to be open.

Or is it different, with only one path needing to be formed between either input and the output?

 

[Mark44]

Am I seeing the problem wrong? I'm seeing a differential signal being put in at the left, and wanting to see the differential signal at the right (after the OP unshorts it). So the series switches all need to be closed, and the parallel shorting switches all need to be open.

Or is it different, with only one path needing to be formed between either input and the output?

This (2nd option) is how I'm interpreting the problem. It might not be the correct interpretation, though.

 

[LCKurtz]

This is an interesting problem, assuming option 2 (transmission line problem). The brute force way of listing the closed paths will surely work but appears error prone with the liklihood of missing a path or two. There are 8 switches so a complete truth table would have 256 lines. I'm thinking of another way and I get 33/128.

Shall we all vote?

[Edit] Running what I thought was a correct circuit simulation I get a very different answer of 39/256. This kind of stuff is an old hobby of mine and I am quite willing to be wrong on one or both. Obviously at least one is wrong, isn't it?

 

[AlephZero]

Think about this first.

--- 1 -------- A
         |
         3
         |
--- 2 -------- B

By counting the 8 switch positions, the probability of signals getting to A and B is

Neither of A or B: 1/4 (switches 1 and 2 both open, 3 doesn't matter)
A but not B: 1/8 (1 closed, 2 and 3 open)
B but not A: 1/8 (2 closed, 1 and 3 open)
Both of A and B: 1/2 (any two switches closed, or all three)

Now find the probabilities of getting through the next 3 switches, then the probability of getting to the end...

 

[uart]

The following attachment is how I think the OP is expecting this interpreted. That is a simple "single wire" interpretation.

I get the following Boolean expression :

[ (A + BC) D + (B + AC) EF ] G + [ (B + AC) E + (A + BC) DF ] H

I'm too lazy to expand that into "min terms' by hand so I made a few lines of code to count them. I found the expression true for 84 out of the 256 possible switch combinations.

 

[dacruick]

Am I seeing the problem wrong? I'm seeing a differential signal being put in at the left, and wanting to see the differential signal at the right (after the OP unshorts it). So the series switches all need to be closed, and the parallel shorting switches all need to be open.

Or is it different, with only one path needing to be formed between either input and the output?

Only one path needs to be open to make it work.

 

[uart]

Only one path needs to be open to make it work.

Yes but you made your diagram unnecessarily confusing by showing two input wires when apparently there was only one. See my revised diagram.

 

[dacruick]

There is vertical symmetry so I'll do the case where only one signal gets through either A or B.

Pr(ADG) + Pr(ADFH) + Pr(ACEH) + Pr(ACEFG) = 1/8 + 1/16 + 1/16 + 1/32 = 9/32
Through symmetry, I can say the same if B is open and A is closed, and that's another 9/32. Since there is a 1/4 chance that both are open I can say 1/4*(18/32)

There are two ways that one switch can be open, and a 1/2 chance that 1 switch will be open. So now I have 2 * 1/2 * (9/32) = 9/32.

So now I have 9/32 * 1/4(18/32)
= 54/128 ?hmmm. what do you guys think?

 

[uart]

I think you're falling into the trap of adding probabilities that are not necessarily mutually exclusive. I'm pretty sure my answer is correct.

 

[uart]

BTW. Here's my Delphi (pascal) code for counting the min-terms.

program tmpswitch;
{$APPTYPE CONSOLE}
uses math;

var a,b,c,d,e,f,g,h,t1,t2 : boolean;
    x : array[0..7] of boolean;
    j,k,m,n : byte;
begin
 n:=0;
 for j:=0 to 255 do
  begin
   for k:=0 to 7 do
    begin
     m := 1 shl k;
     x[k] := m = (m and j);
    end;
   a:=x[0]; b:=x[1]; c:=x[2]; d:=x[3]; e:=x[4]; f:=x[5]; g:=x[6]; h:=x[7];
   t1 := (a or b and c) and d or (b or a and c) and e and f ;
   t2 := (b or a and c) and e or (a or b and c) and d and f;
   if (t1 and g) or (t2 and h) then n:=n+1;
  end;
 writeln(n);
end.

 

[dacruick]

The following attachment is how I think the OP is expecting this interpreted. That is a simple "single wire" interpretation.

I get the following Boolean expression :

[ (A + BC) D + (B + AC) EF ] G + [ (B + AC) E + (A + BC) DF ] H

I'm too lazy to expand that into "min terms' by hand so I made a few lines of code to count them. I found the expression true for 84 out of the 256 possible switch combinations.

let me clarify something here with you. Referring to the first term, if I add (A + BC) I get 3/4. But that is not the probability of signal getting to D. The probability is 5/8. So using that and your "equation" I have 30/64.

 

[LCKurtz]

Good morning everyone. I found an error in my probability calculations and I now agree with uart that the probability is 84/256. Here's my probability calculations, using the labelling uart uses. I used the following boolean expression:

c'f'(adg+beh) + cf'(a+b)(dg+eh) + c'f(ad+be)(g+h) + cf(a+b)(d+e)(g+h)

Here's the probability for each term:

c'f'(adg+beh): 1/2*1/2*(1/8+1/8-1/64) = 15/256

cf'(a+b)(dg+eh): 1/2*1/2*(1/2+1/2-1/4)(1/4+1/4-1/16) = 21/256

c'f(ad+be)(g+h): 1/2*1/2*(1/4+1/4-1/16)(1/2+1/2-1/4) = 21/256

cf(a+b)(d+e)(g+h): 1/2*1/2*(1/2+1/2-1/4)³ = 27/256

Total: 84/256.

 

[uart]

let me clarify something here with you. Referring to the first term, if I add (A + BC) I get 3/4. But that is not the probability of signal getting to D. The probability is 5/8. So using that and your "equation" I have 30/64.

Hi dacruick. That expression of mine does not represent probabilities. It is a Boolean expression describing what logical function of the switch combinations is the output. In other words (A + BC) represents "A or (B and C)" etc. So let's be clear, it is a logical expression not a numerical expression.

 

[dacruick]

Good morning everyone. I found an error in my probability calculations and I now agree with uart that the probability is 84/256. Here's my probability calculations, using the labelling uart uses. I used the following boolean expression:

c'f'(adg+beh) + cf'(a+b)(dg+eh) + c'f(ad+be)(g+h) + cf(a+b)(d+e)(g+h)

Here's the probability for each term:

c'f'(adg+beh): 1/2*1/2*(1/8+1/8-1/64) = 15/256

cf'(a+b)(dg+eh): 1/2*1/2*(1/2+1/2-1/4)(1/4+1/4-1/16) = 21/256

c'f(ad+be)(g+h): 1/2*1/2*(1/4+1/4-1/16)(1/2+1/2-1/4) = 21/256

cf(a+b)(d+e)(g+h): 1/2*1/2*(1/2+1/2-1/4)³ = 27/256

Total: 84/256.

would you mind explaining the logic behind the last 3 terms to me? I understand the first one no problems.

 

[dacruick]

Hi dacruick. That expression of mine does not represent probabilities. It is a Boolean expression describing what logical function of the switch combinations is the output. In other words (A + BC) represents "A or (B and C)" etc. So let's be clear, it is a logical expression not a numerical expression.

What about the case A and (B and C)? Where does that case get taken care of?

 

[LCKurtz]

would you mind explaining the logic behind the last 3 terms to me? I understand the first one no problems.

Are you asking about where the terms in the Boolean expression came from or the associated probability calculations?

 

[uart]

What about the case A and (B and C)? Where does that case get taken care of?

Hi dacruick. The Boolean expression "A OR (B AND C)" evaluates to "true" when ever "A" is true OR whenever "B" and "C" are both true. So it certainly covers the case when "A" "B" and "C" are all true. In Boolean algebra (and in general computer and digital logic) OR covers the "Either OR" situation. That is "X OR Y" is true if either "X" is true OR if "Y" is true OR if both are true.

 

[dacruick]

Hi dacruick. The Boolean expression "A OR (B AND C)" evaluates to "true" when ever "A" is true OR whenever "B" and "C" are both true. So it certainly covers the case when "A" "B" and "C" are all true. In Boolean algebra (and in general computer and digital logic) OR covers the "Either OR" situation. That is "X OR Y" is true if either "X" is true OR if "Y" is true OR if both are true.

okay thanks for clearing that up.

Are you asking about where the terms in the Boolean expression came from or the associated probability calculations?

If you give me the associated probability, I should be able to figure out where the expression came from. :)

 

[LCKurtz]

Good morning everyone. I found an error in my probability calculations and I now agree with uart that the probability is 84/256. Here's my probability calculations, using the labelling uart uses. I used the following boolean expression:

c'f'(adg+beh) + cf'(a+b)(dg+eh) + c'f(ad+be)(g+h) + cf(a+b)(d+e)(g+h)

Here's the probability for each term:

c'f'(adg+beh): 1/2*1/2*(1/8+1/8-1/64) = 15/256

cf'(a+b)(dg+eh): 1/2*1/2*(1/2+1/2-1/4)(1/4+1/4-1/16) = 21/256

c'f(ad+be)(g+h): 1/2*1/2*(1/4+1/4-1/16)(1/2+1/2-1/4) = 21/256

cf(a+b)(d+e)(g+h): 1/2*1/2*(1/2+1/2-1/4)³ = 27/256

Total: 84/256.

Are you asking about where the terms in the Boolean expression came from or the associated probability calculations?

would you mind explaining the logic behind the last 3 terms to me? I understand the first one no problems.

If you give me the associated probability, I should be able to figure out where the expression came from. :)

I did explain all the probabilities. See the copy a few lines up.

 

[dacruick]

I was hoping you would explain with words. The term (a+b) has a probability of 3/4 is what you're saying. If that's the probability that either a or b is open, you're then multiplying it by the probability that dg or eh is open? Thats what I don't understand.

 

[LCKurtz]

I was hoping you would explain with words. The term (a+b) has a probability of 3/4 is what you're saying. If that's the probability that either a or b is open, you're then multiplying it by the probability that dg or eh is open? Thats what I don't understand.

OK, I will explain how I got it. Here's a figure:

The switches at c and f are causing the problem by interrupting the "and-or" structure. So the idea is to break the circuit down into the four cases for switches c and f. Look at the second figure. Here I have illustrated the circuit where c is closed and f is open. In that picture you have a connection through the first section if a or b is closed; write that:

(a + b)

You have a connection through the second part of the circuit if either g and d are closed or e and h are closed. Write that:

(gd + eh)

To get a complete circuit you need the first half and the second half:

(a+b)(gd + eh)

Finally, this is all given c closed and f open, write that

cf'

You need them all true for this case, which gives the term:

cf'(a+b)(gd + eh)

That's how I got the second term of the expansion. There are three more states for cf. So see if you can draw the corresponding circuits and get the correct expressions.

[Edit] fixed typo cd should have been gd

 

[dacruick]

OK, I will explain how I got it. Here's a figure:

The switches at c and f are causing the problem by interrupting the "and-or" structure. So the idea is to break the circuit down into the four cases for switches c and f. Look at the second figure. Here I have illustrated the circuit where c is closed and f is open. In that picture you have a connection through the first section if a or b is closed; write that:

(a + b)

You have a connection through the second part of the circuit if either c and d are closed or e and h are closed. Write that:

(cd + eh)

To get a complete circuit you need the first half and the second half:

(a+b)(cd + eh)

Finally, this is all given c closed and f open, write that

cf'

You need them all true for this case, which gives the term:

cf'(a+b)(cd + eh)

That's how I got the second term of the expansion. There are three more states for cf. So see if you can draw the corresponding circuits and get the correct expressions.

Thank you, that's perfect. Thanks to uart too.