How would you calculate the probability of matching the value of a sequenced list?

Question

Suppose we have a sequence of items, from an alphabet of 2: {0,1}. For example, this 8-bit sequence: 10001010

You generate a random 8-bit string. The probability of you matching the first bit is $1/2$ or 50%, the last bit also $1/2$ or 50%, and of matching both: $1/2 * 1/2$ or 25%.

Part 1 concerns how many attempts someone would have to make to have the first and last bit match.

1. Intuitively, it seems like 4 attempts would yield a high probability of achieving this match. But statistics is not always intuitive...

Part 2 concerns any particular bit in the sequence, but trying to match the most number possible.

1. What is the probability of matching any bit correctly? (Of matching any $n$ bits correctly?)
2. How many random generations would someone need to make to reach $n$ bit matches with probability=$1/2$? (With probability=$3/4$?)

Answer 1

For the 1st part you should probably learn more about the geometric distribution and possibly the negative binomial distribution.

The geometric distribution models the number of independent trials needed before you see the first success (or sometimes the number of failures before the 1st success). The negative binomial is an extension of this, it is how many trials (or failures) before seeing $k$ successes (the geometric is a special case with $k=1$). So with a 25% chance of success on each try (agreeing with your computations and assuming each trial is independent) then the probability (based on the geometric) of matching the 1st and last in 4 tries or less is only about 68%, is that a "High Probability"? to get over 95% you need 11 tries.

For part 2.1 this is easiest to compute as the opposite of matching 0 correctly. So for each of 8 bits there is a 50% chance of not matching it, so the probability of not matching any is $0.5^8$ and the probability of matching any (at least one) is therefore $1-0.5^8 = 0.996$.

The probability of matching exactly $n$ bits (but not caring which $n$) will follow the binomial distribution.

For 2.2 you can now combine the binomial and geometric distributions (if I understand it correctly and the assumptions hold).

This all assumes that each try is independent, we don't learn anything from the previous try, just if it succeeded or failed.

If we learn something each time, such as that on the first try I found the 1st digit, but don't know on the rest (and it will not change for the 2nd try) then this becomes more like the coupon collectors problem.