Forum Index Register Members List Events Mark Forums Read Help

 JREF Forum A probabilities question

 Welcome to the JREF Forum, where we discuss skepticism, critical thinking, the paranormal and science in a friendly but lively way. You are currently viewing the forum as a guest, which means you are missing out on discussing matters that are of interest to you. Please consider registering so you can gain full use of the forum features and interact with other Members. Registration is simple, fast and free! Click here to register today.

 24th May 2012, 03:23 AM #1 LandR Graduate Poster     Join Date: Sep 2009 Posts: 1,028 A probabilities question I'm doing a free online crypto course and one of the exercises we had contained this question. I got it wrong and don't know how to actually work it out. The question: Let X be a uniform random variable over the set {0,1}n (That is X is a random string of bits of length n.) Let Y be a random variable over the set {0,1}n (Not necessarily uniform). Y is independent of X Define Z as X xor Y. What is the probability that Z equals 0n ? Anyone help me understand how to solve this problem ?
 24th May 2012, 03:48 AM #2 Marras Scholar   Join Date: Apr 2012 Posts: 97 Originally Posted by LandR Anyone help me understand how to solve this problem ? Let's look it one bit a time. The probability that the first bit of Z is 0 is the probability that the xor of first bits of X and Y is zero. The xor is zero if either both of the bits are zero or if they both are one. Since X and Y are independent with each other and both cases are distinct, the probability can be computed using just multiplication and addition. So, we get: P(first bit of Z is 0) = P(first bit of X is 0 and first bit of Y is 0) + P(first bit of X is 1 and first bit of Y is 1) As X is uniform both possible values for its first bit have the same probability 0.5. The probability for the first bit of Y is not known, but let's say that it's zero with the probability p and one with probability (1 - p). Then, the probability comes up as: P(first bit of Z is 0) = 0.5*p + 0.5 * (1-p) A bit of algebraic manipulation will give you the result, and you can then generalize it to the case of n-bit messages.
 24th May 2012, 04:13 AM #3 ddt Mafia Penguin     Join Date: Dec 2007 Location: Netherlands Posts: 10,323 Originally Posted by LandR I'm doing a free online crypto course and one of the exercises we had contained this question. I got it wrong and don't know how to actually work it out. The question: Let X be a uniform random variable over the set {0,1}n (That is X is a random string of bits of length n.) Let Y be a random variable over the set {0,1}n (Not necessarily uniform). Y is independent of X Define Z as X xor Y. What is the probability that Z equals 0n ? Anyone help me understand how to solve this problem ? As the previous poster already explained, for Z to be 0n, the bits in X must be equal to the respective bits in Y. The easiest way to look at this is: First look at the value of Y. Then for the desired outcome, X must be equal to Y. As X is independent of Y, and X is uniform, this probability is 2-n, irrespective of the value of Y you began with. So the probability is 2-n. Alternatively, you could write a sum over all possible outcomes of Y and write out the conditional probabilities and come to the same conclusion. __________________ Proud member of the Solipsistic Autosycophant's Group
 24th May 2012, 07:00 AM #4 LandR Graduate Poster     Join Date: Sep 2009 Posts: 1,028 Originally Posted by Marras Let's look it one bit a time. The probability that the first bit of Z is 0 is the probability that the xor of first bits of X and Y is zero. The xor is zero if either both of the bits are zero or if they both are one. Since X and Y are independent with each other and both cases are distinct, the probability can be computed using just multiplication and addition. So, we get: P(first bit of Z is 0) = P(first bit of X is 0 and first bit of Y is 0) + P(first bit of X is 1 and first bit of Y is 1) As X is uniform both possible values for its first bit have the same probability 0.5. The probability for the first bit of Y is not known, but let's say that it's zero with the probability p and one with probability (1 - p). Then, the probability comes up as: P(first bit of Z is 0) = 0.5*p + 0.5 * (1-p) A bit of algebraic manipulation will give you the result, and you can then generalize it to the case of n-bit messages. Thank you, I think I'm still a bit confused. So for one bit the probability is: 0.5*p + 0.5 * (1-p) = 0.5p + 0.5- 0.5p = 0.5 So, for each additional bit it would be 0.5 * 0.5. So for 2 bits it would be 0.25 For 3 bits it would be 0.125 So the probability would be 0.5n ? Originally Posted by ddt So the probability is 2-n. Oh! The options on the course quiz were: , , , and 0.5. Oh, I just realised. 1 / 2n is 0.5n and 2-n. Thank you for the help! Last edited by LandR; 24th May 2012 at 07:03 AM. Reason: Me being stupid!
 24th May 2012, 07:05 AM #5 LandR Graduate Poster     Join Date: Sep 2009 Posts: 1,028 One more point though, what if X and Y were both uniform random variables ? Wouldn't the probability just be the same ? I don't understand the point of why it was stated that Y is not necessarily uniform..
 24th May 2012, 07:10 AM #6 edd Graduate Poster     Join Date: Nov 2007 Posts: 1,557 Originally Posted by LandR One more point though, what if X and Y were both uniform random variables ? Wouldn't the probability just be the same ? I don't understand the point of why it was stated that Y is not necessarily uniform.. It's a crypto course - I presume Y could be message data or some untrusted source or generally something you don't have control of. __________________ When I look up at the night sky and think about the billions of stars out there, I think to myself: I'm amazing. - Peter Serafinowicz
 24th May 2012, 07:25 AM #7 Marras Scholar   Join Date: Apr 2012 Posts: 97 Originally Posted by LandR I don't understand the point of why it was stated that Y is not necessarily uniform.. The point of that exercise is to show that one-time-pad method of cryptography is provably secure. That is, if you have a uniformly random key that is as long as the message, there is no way to crack the encrypted message. Here X is the random key and Y is the non-random message, stated in a slightly different way. No matter what the Y is, if X is random, the output is random. Even though one-time-pad is provably secure, its real implementations can have flaws that make it possible to break it. For example, if X is not truly random it may be possible to decode parts or the whole message. Another flaw is that if you use a completely random X to crypt two different messages Y1 and Y2, both can be trivially cracked.
 24th May 2012, 07:44 AM #8 LandR Graduate Poster     Join Date: Sep 2009 Posts: 1,028 If anyone is interested, here is the course https://www.coursera.org/course/crypto I thought it was very interesting. There were a lot of topics covered and each week had a quiz of 10 or so questions based on the material and interesting programming assignments. The material was very good quality I thought for a free course and I learned a lot. Although I won't claim to understand the math content!
 24th May 2012, 08:19 AM #9 ddt Mafia Penguin     Join Date: Dec 2007 Location: Netherlands Posts: 10,323 Originally Posted by LandR One more point though, what if X and Y were both uniform random variables ? Wouldn't the probability just be the same ? I don't understand the point of why it was stated that Y is not necessarily uniform.. And to add to the other answers: when setting up and proving a mathematical theorem, you try to have as few assumptions as possible in the theorem. Even when you don't (yet) need that general case. __________________ Proud member of the Solipsistic Autosycophant's Group

JREF Forum

 Bookmarks Digg del.icio.us StumbleUpon Google Reddit