# GATE | GATE-CS-2005 | Question 52

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
(A) 1/2n
(B) 1 – (1/n)
(C) (1/n!)
(D) 1 – (1/2n)

Explanation: <!–

```The probability that the two strings are identical is
(1/2) * (1/2) * ..... * (1/2) (n times) which is 1/2n

The probability for not identical is 1 - (1/2n)```

–>

let us suppose if outcome is head =>0, tail => 1
Since the coin is fare, P(H) = P(T) = 1⁄2
Length of the string is => n

P(X) = both the strings should not be identical

P(-X) = both are not identical = 1 – P(X)

If both the strings are equal, every character should be same w.r.t its positions

i.e P(X) = 1/2*1/2*…….(n times) = (1/2)^n

P(-X) = 1 – (1/2)^n

This solution is contributed by Anil Saikrishna Devarasetty

Quiz of this Question

My Personal Notes arrow_drop_up

## Recommended Posts:

Article Tags :

Be the First to upvote.

Please write to us at contribute@geeksforgeeks.org to report any issue with the above content.
{"ft_lang_label":"__label__en","ft_lang_prob":0.9086316,"math_prob":0.9879489,"size":939,"snap":"2020-34-2020-40","text_gpt3_token_len":308,"char_repetition_ratio":0.12192513,"word_repetition_ratio":0.0,"special_character_ratio":0.34824282,"punctuation_ratio":0.0882353,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9948536,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-08-12T10:39:18Z\",\"WARC-Record-ID\":\"<urn:uuid:bfade130-85e2-4256-b456-76aa6e5040cc>\",\"Content-Length\":\"90898\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:5ecf3e34-cb58-4520-8457-3f49ff684674>\",\"WARC-Concurrent-To\":\"<urn:uuid:cded5a21-68b4-4edd-9703-7943b6031e30>\",\"WARC-IP-Address\":\"23.215.132.80\",\"WARC-Target-URI\":\"https://www.geeksforgeeks.org/gate-gate-cs-2005-question-52/\",\"WARC-Payload-Digest\":\"sha1:WJ2EGJTEGOMYL4MWNZQ5AIPY3T42MNZR\",\"WARC-Block-Digest\":\"sha1:EKRG3TV2PP4GGK3RCFUUXM436ZIDXIMN\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-34/CC-MAIN-2020-34_segments_1596439738888.13_warc_CC-MAIN-20200812083025-20200812113025-00539.warc.gz\"}"}