0
$\begingroup$

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.

  • 0
    I can't parse "We add item l_i to a set of l_i's toss came up heads".2011-04-11
  • 0
    Yes it is (that simple). Of course, joint laws are more complicated, for instance two neighbors cannot both be chosen.2011-04-11
  • 0
    @Alon Amit: Wow, sorry. Must be early. If the toss came up heads2011-04-11
  • 0
    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$.2011-04-11
  • 0
    @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.2011-04-11
  • 0
    @joriki: I hope my edit improves the question. *if/of* also changed2011-04-11
  • 0
    @Alon Amit: The role of items are as a generic 'term'. We could think of them themselves as coin tosses (rather than having a coin toss associated with it) and if toss i-1 and i+1 are tails, while toss i is heads, then we write that toss number down on a piece of paper. What is the probability that it is written on the paper? (and following from that, what are the expected number of tosses written on the page)2011-04-11

1 Answers 1

4

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.

  • 0
    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.2011-04-11
  • 0
    @joriki: But, by linearity of expectation, shouldn't this still be n/8? How does the conditionality of this change the problem?2011-04-11
  • 0
    @shoes: $n/8$ look right to me. The dependency might affect the variance, but it should not affect the expectation.2011-04-11
  • 0
    @shoes, @Henry: Sorry, I've deleted my braindead comment about the expectation value being influenced by the correlations.2011-04-11