in Probability
8,314 views
27 votes
27 votes

A random bit string of length n is constructed by tossing a fair coin n times and setting a bit to 0 or 1 depending on outcomes head and tail, respectively. The probability that two such randomly generated strings are not identical is:

  1. $\frac{1}{2^n}$
  2. $1 - \frac{1}{n}$
  3. $\frac{1}{n!}$
  4. $1 - \frac{1}{2^n}$
in Probability
by
8.3k views

2 Comments

Total possible selections ((2n)C1 ) * ((2n)C1 ) . Favorable outcomes   (2n) * (2n-1)

7
7

tot prob

= 1st bits mismatch + 1st bits match and 2nd bits mismatch + ….+ first n-1 bits match and nth bits mismatch

=½ + (½ )^2 + …. + (½) ^n 

= 1 – (½ )^2

0
0

11 Answers

0 votes
0 votes

 

Take small values for n and then solve it.

 

0 votes
0 votes

Using simple probability concept,

Suppose we take a n-bit string. Now looking into the sample space, if we want the same string again, we only have $1$ possibility.

Now, sample space = $2^n$ [combinations of n-bit strings]

Probability to get same identical string = $\frac{1}{2^n}$

But we want the opposite.

Therefore, $1-\frac{1}{2^n}$

This returns the probability of atleast one character that will be different from the original string. 

–2 votes
–2 votes
Favourable case is 1 and the total sample space is $2^n$ so it must be $1/2^n$

2 Comments

Read the question once ! Answer should be D .
0
0
total strings that can be generated are 2^(n)

((2^(n)) * (2^(n) - 1)) / ( 2^(n) * 2^(n))

1- (1/2^(n))

in total outcomes for first string it can be any amongst 2^(n) and similar for choosing second string
0
0
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true