2 votes 2 votes Three $N$ bit binary strings $S_1$,$S_2$,$S_3$ are selected in random. What is the probability that result of bit-wise XOR among them contains $k$ $1$'s.i.e. $S_1\oplus S_2\oplus S_3$ = $S$ , No of set bits in $S$ = $k$ is it $\binom{n}{k}\left ( \frac{1}{2} \right )^k\left ( \frac{1}{2} \right )^{n-k}$ ?? Probability probability + – dd asked Feb 8, 2017 • edited Feb 8, 2017 by dd dd 679 views answer comment Share Follow See 1 comment See all 1 1 comment reply yg92 commented Feb 8, 2017 reply Follow Share @Debashish why binomial distribution? HyperGeometry can be applied? nCk/2n 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes I think your formula is valid bcoz we want odd number of 1's, hence (1,1,1), (0,0,1),(0,1,0),(1,0,0) are the possibilites making 4/8 as succes probability or 1/2. So for k bits to be set nCk (1/2)k(1/2)n-k Rahul Jain25 answered Feb 8, 2017 Rahul Jain25 comment Share Follow See all 4 Comments See all 4 4 Comments reply dd commented Feb 8, 2017 reply Follow Share And trials are three bit tuples rt?? 0 votes 0 votes Rahul Jain25 commented Feb 8, 2017 reply Follow Share Yes bcoz Xor is done for 3 binary number and will be done bitwise. Correct me if any mistakes☺ 0 votes 0 votes dd commented Feb 8, 2017 reply Follow Share What I am doing is collect $N$ tuples each of $3$ bit to select $3$ strings. If they ask for four strings I would have collected $4$ bit tuples $n$ times. And now like you said each tuple has probability $1/2$ to get XOR result $1$. Thus we get the above formula. 0 votes 0 votes Rahul Jain25 commented Feb 8, 2017 reply Follow Share Yes exactly, since it is bitwise operation each bits are independent of each other, so we can use this formula. There are 4 tuples in success set here, and total possible tuples are 8. So success probability is 1/2, probability of each tuple is going to be 1/8 bcoz it is 3-tuple. 0 votes 0 votes Please log in or register to add a comment.