Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am studying for an exam and found the following problem.

Let $L = l_0, l_1, ... , l_{n+1}$ be a list of items. For each item from 0 to $n+1$, we flip a coin (fairly). We add item $l_i$ (with $1 \le i \le n$) to a set if $l_i$'s toss came up heads, and both of its neighbours ($l_{i - 1}$ and $l_{i + 1}$) came up tails. What is the probability that $l_i$ is included in the set?

My initial thought is that it is simply 1/8. The probability that the coin is heads is 1/2, the one before it being tails has probability 1/2, and the same idea for the toss after it. Am I missing something, or is it really that simple? They are obviously dependent on one another.

share|cite|improve this question
I can't parse "We add item l_i to a set of l_i's toss came up heads". – Alon Amit Apr 11 '11 at 16:10
Yes it is (that simple). Of course, joint laws are more complicated, for instance two neighbors cannot both be chosen. – Did Apr 11 '11 at 16:10
@Alon Amit: Wow, sorry. Must be early. If the toss came up heads – user9448 Apr 11 '11 at 16:14
There seems to be a slight mistake in the problem statement. If coins are only flipped for items $1$ to $n$, then there's no coin for $0$ and $n+1$ to use in deciding whether to include $1$ and $n$. It looks like what they meant is that a coin is flipped for each item from $0$ to $n+1$, and then the decision rule is applied for each item from $0$ to $n$. – joriki Apr 11 '11 at 16:15
@shoes: it's not just the missing "if" - I don't understand what's the role of the "items" in the problem and what "adding l_i to a set of l_i's" means. I guess I can imagine what this is trying to say but since you're asking if there's any subtlety here, you really ought to make the question very precise. – Alon Amit Apr 11 '11 at 16:17
up vote 4 down vote accepted

If that's the whole question, yes, it really is that simple. Perhaps there's a part (b)...

On the other hand, maybe this is intended to test the student's ability to filter out irrelevant aspects of the problem. This is actually a significant issue with many probability students, who might insist on using a sample space involving all $n+2$ coin flips.

share|cite|improve this answer
You're right. There is a part b. It is to compute the expected size of the list. This seems trivial if you're given the probability, though. – user9448 Apr 11 '11 at 16:13
@joriki: But, by linearity of expectation, shouldn't this still be n/8? How does the conditionality of this change the problem? – user9448 Apr 11 '11 at 16:22
@shoes: $n/8$ look right to me. The dependency might affect the variance, but it should not affect the expectation. – Henry Apr 11 '11 at 16:26
@shoes, @Henry: Sorry, I've deleted my braindead comment about the expectation value being influenced by the correlations. – joriki Apr 11 '11 at 16:44

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.