83
$\begingroup$

In this article, the winner of the math competition answered this question correctly:

In a barn, 100 chicks sit peacefully in a circle. Suddenly, each chick randomly pecks the chick immediately to its left or right. What is the expected number of unpecked chicks?

The answer was given as 25. I am interested to know the correct method for solving this problem as well as a general way to find this out for N chicks. I was thinking of trying to solve by figuring out the number of occurrences of (something?) inside a binary string of length 100 (or N), but I don't know if that is the right way to approach it.

$\endgroup$
  • 4
    $\begingroup$ This was just posted on the Mind Your Decisions Youtube channel, with a full general solution too as the question is not properly stated. (Random but what distribution?) $\endgroup$ – JDługosz May 16 '17 at 20:02
  • 1
    $\begingroup$ @JDługosz Indeed, for Carmeister's solution to apply, we need that each chick follows a uniform distribution and that chicks $i$ and $i+2$ are independent. $\endgroup$ – Hagen von Eitzen May 18 '17 at 22:27
  • $\begingroup$ See also Brian Hayes' blog, bit-player.org/2017/counting-your-chickens-before-theyre-pecked $\endgroup$ – Gerry Myerson Oct 12 '17 at 8:33
210
$\begingroup$

For any individual chick, there is a $0.5$ chance that the one on its right won't peck it, and a $0.5$ chance that the one on its left won't peck it. So overall, it has a $0.25$ chance of not being pecked.

Since this is true for every chick, we can add up $0.25(100)=25$ to get the number of unpecked chicks.

"But wait," you might say, "the probabilities that chicks are unpecked aren't independent! If chick $n$ is unpecked, then chicks $n-2$ and $n+2$ will be pecked. Surely we have to take this into account!"

Fortunately, there's a very useful theorem called linearity of expectation. This tells us that for any random variables $X$ and $Y$, independent or not, $E[X+Y]=E[X]+E[Y]$, where $E$ is the expected value. What we're formally doing above is assigning a random variable $X_i$ to the $i$th chick that is equal to $0$ if the chick is pecked and $1$ if it's unpecked. Then the total number of unpecked chickens is $\sum X_i$, so the expected number of unpecked chickens is $$E\left[\sum X_i\right]=\sum E[X_i]$$ by linearity of expectation. But $E[X_i]$ is just the probability that the $i$th chicken is unpecked, thus justifying our reasoning above.

$\endgroup$
  • 161
    $\begingroup$ This answer is impeccable. $\endgroup$ – Will Jagy May 16 '17 at 0:29
  • 27
    $\begingroup$ @WillJagy -- take your lousy upvote, you animal. $\endgroup$ – Malvolio May 16 '17 at 2:37
  • 3
    $\begingroup$ In spite of the comment by @WillJagy, I find "to get the number of unpecked chicks" sloppy formulation. You don't get that number, just the expected value for that number. It is not necessarily the most likely value for that number, or even a possible value for that number (in this case it clearly is the latter, but it would not have been for a number of chicks not divisible by $4$). $\endgroup$ – Marc van Leeuwen May 17 '17 at 7:31
  • 2
    $\begingroup$ ......., qui tollis peccata mundi, miserere nobis. $\endgroup$ – Will Jagy May 17 '17 at 16:38
  • 1
    $\begingroup$ @AkshatMahajan Since $X_i$ can be either $0$ or $1$, $E[X_i]=1\cdot P(X_i=1)+0\cdot P(X_i=0)=P(X_i=1)$. $\endgroup$ – Carmeister May 18 '17 at 22:25
15
$\begingroup$

This is a simple problem. Look, ma, no equations!

Consider YOU are the only chicken that matters, and construct a table to say whether YOU get pecked. Your chance of being pecked comes down to only 4 outcomes. (1) YES - pecked twice. (2) YES - pecked from left wing only. (3) YES - pecked from right wing only. (4) NO - unpecked.

The table has 4 elements, all of equal probability, 1 of which is unpecked. YOU are therefore pecked 3:1 ratio or 3:4 opportunities or 75% of the time. For convenience, this needs to be conducted for 100 trials of YOU, and the answer is that 25 times YOU will NOT be pecked. The circular nature of the 100 chicks says that YOU are not unique, and your experience is the same as the others, so we extrapolate your experience of 100 trials to a single trial of 100 chicks just like YOU.

25 unpecked chicks, 50 get pecked once, 25 get double pecks.

This is the same table constructed for 100 women having two children and asking how many have no girls.

$\endgroup$
  • 4
    $\begingroup$ The question is about an expected value, not about a probability; an answer should address the notion of expected value at some point, which this one does not. One can even read this answer as saying that 25 is a certain outcome, which of course it is not. And talking about trials suggests independent probabilities for each trial, which is not the case here. $\endgroup$ – Marc van Leeuwen May 17 '17 at 7:47
  • 2
    $\begingroup$ I disagree with the previous comments protesting the correctness of this answer. I think this is exactly the right intuition behind linearity of expectation, and it holds up as a formal argument. The argument is: the total number of unpecked chicks counts, for each chick, whether they were pecked or not. Since all chicks are the same as me, I can just count whether or not I would be pecked or not in 100 trials. Then the expected value of that is clearly 25. $\endgroup$ – 6005 May 18 '17 at 1:58
  • 3
    $\begingroup$ @6005 Yes, I believe the argument is non-rigorous. It gives no reason why the sum over 100 chicks should give the same result as the sum over 100 trials of one chick, and indeed for other properties the two sums are not the same. If you do know the correct reason why the sum works, you don't need to appeal to the 100 repetitions of one chick. $\endgroup$ – David K May 19 '17 at 2:21
  • 2
    $\begingroup$ @Wildcard Sorry, all this back and forth in comments has led to a lot of unclear references. What I meant was, the number of times a chick is unpecked in 100 trials is a sum of indicator variables; so is the number of unpecked chicks among 100 chicks in one trial. The two sums have the same expectation, but (for example) different variances. So if we want to know something about the 100 chicks, in general we can't just measure the same property over 100 trials of one chick and "extrapolate" to the 100 chicks as argued in the answer above. For expectation, however, we can invoke linearity. $\endgroup$ – David K May 19 '17 at 14:01
  • 2
    $\begingroup$ @Wildcard: A simpler property than "variance" that is different between the two cases is "highest possible outcome" of the random variables. One chicken with 100 trials can end up unpecked 100 times with a small but nonzero probabilty. For one trial with 100 chickens, it is impossible for all 100 to be unpecked. $\endgroup$ – Henning Makholm May 19 '17 at 16:15
10
$\begingroup$

It is overkill for this, but you can write a simulation to estimate the expected number. Such a simulation doesn't prove anything per se, but sometimes it is useful to write a quick simulation to confirm that a probability calculation is correct. Here is one in R:

count.unpecked <- function(n){
  chicks <- 0:(n-1)
  pecks <- sample(c(-1,1),n,replace = TRUE)
  pecked <- (chicks + pecks) %% n
  n - length(unique(pecked))
}

print(mean(replicate(100000,count.unpecked(100))))

This simulates the experiment 100,000 times. Output from my last run: 25.00679

$\endgroup$
7
$\begingroup$

It is possible to have a state with $50$ unpecked chicks. It's also possible to have $0$ unpecked chicks and any integer between $0$ and $50$ is possible. $51$ unpecked chicks is impossible because then there would be no way to have $100$ pecks totally. If we can show that having $x$ unpecked chicks is equally likely as having $50-x$ unpecked chicks, then the average of both scenarios gives you $25$ unpecked chicks. So you number the chicks $1$ to $100$ such that consecutive numbers are adjacent to each other and $1$ is next to $100$. Change the directions of each chick that is divisible by $4$ and each chick that is congruent to $1 \mod 4$. I believe this involution gives us a one to one correspondence between states with $x$ unpecked chicks and states with $50-x$ unpecked chicks. Each state is equally likely and this means that $25$ has to be the expected number of unpecked chicks.

My explanation only works when the total number of chicks is positive and divisible by $4$. Luckily, $100$ is divisible by $4$.

$\endgroup$
  • 1
    $\begingroup$ chicks, not children $\endgroup$ – Marc van Leeuwen May 17 '17 at 7:15
  • 3
    $\begingroup$ The P(x)=P(50-x) part can probably be shown by considering the situation of 100 children in a circle, each having a red&green ball at the start. Each child randomly gives one ball to both neighbours, and in turn receives two balls from them. Obviously, the chance of ending with two green balls is the same as the chance of ending with two red balls. $\endgroup$ – MSalters May 17 '17 at 13:19
  • 1
    $\begingroup$ Great alternate answer, although the fact it only applies if $4 \mid n$ does diminish it slightly. $\endgroup$ – 6005 May 19 '17 at 23:15
  • 1
    $\begingroup$ The way to think about it for $n = 2k$ is that the chicks split into two circles of $k$ chicks (odd-numbered and even-numbered). For each pair of adjacent chicks in one of the two circles, one of them gets pecked (either left or right chick). So, we have two circles of k pecks, where each peck is either L or R. Then, the number of unpecked chicks is the number of times we see the sequence LR in one of the circles -- which is half the total number of switches (LR or RL). $\endgroup$ – 6005 Jun 9 '17 at 3:51
  • 1
    $\begingroup$ @JohnColeman There should be an exponent of $x$, there, yes. The comment I just wrote may start to address where I got those formulas. For $n = 2k$ there are $2^{2k}$ possible pecking arrangements, so let's argue the number of ones with $x$ unpecked chicks is $2 \binom{2k}{2x} + 2 (-1)^{x} \binom{k}{x}$. From the previous comment, we need to choose $2x$ places to switch from $L$ to $R$ or vice versa, but we need an even number of switches in each circle, and we also need to multiply by 4 since for a given arrangement of switches in a circle, there are two ways to choose corresponding [contd] $\endgroup$ – 6005 Jun 9 '17 at 4:15
5
$\begingroup$

Consider the even numbered chicks, and ask the expectation of how many odd chicks are unpecked plus the number that are double pecked. If we create a random walk with step $k$ growing left if chick $2k$ pecks left, then we see that the number of unpecked or double-pecked odd chicks is the number of sign changes in a cyclical sequence of length 50. The expectation for that is 25. SO the number of unpecked chickes is half that, or 12.5. Adding, now the even chicks, we get the answer of $12.5\times 2=25$.

$\endgroup$
  • $\begingroup$ How do you know for certain that double-pecking and unpecking will occur with equal probability? I'm referring to where you say "The expectation for that is 25. SO the number of unpecked chickes is half that, or 12.5." $\endgroup$ – AAC May 15 '17 at 22:04
  • $\begingroup$ @AAC They have the same probability because they are completely dependent on each other. In fact they are exactly equal. Since we have 100 pecks no matter what, a double peck in one chicken must mean than some other chicken will be unpecked (and vice versa). $\endgroup$ – Thanassis May 17 '17 at 2:29
  • 2
    $\begingroup$ You seem to base the outcome of this easy problem on a (seemingly?) much deeper fact about random walks (the expected number of sign changes in a closed walk on the integers), which is kind of curious. If anything I would use the argument in the opposite direction. $\endgroup$ – Marc van Leeuwen May 17 '17 at 7:54
2
$\begingroup$

The probability that a chick is unpecked is the probability that its left neighbors pecks left and its right neighbor pecks right. Assuming that each chick chooses left or right with probability $0.5$ and that choices are independent, you get the result.

The number of chicks doesn't affect the $0.25$ probability as long as it is greater than $2$.

$\endgroup$
  • 1
    $\begingroup$ The question is about an expected value, not about a probability; an answer should address the notion of expected value at some point, which this one does not. And the argument only uses that the choices for pairs of chicks at distance two of each other are independent of each other, so that the "25% chance for each chick" is justified. $\endgroup$ – Marc van Leeuwen May 17 '17 at 7:26
  • 1
    $\begingroup$ @MarcvanLeeuwen If this were homework, I'd agree with you. $\endgroup$ – Fabio Somenzi May 17 '17 at 14:06
2
$\begingroup$

I tried to reduce complexity to adjust it to my intellectual competence, so I considered 4 chicken in an event matrix. That shows:

  • the probability that 2 chicken (50 %) remain unpecked is 0.25
  • the probability that 1 chicken (25 %) remains unpecked is 0.5
  • the probability that no chicken (0 %) remains unpecked is 0.25
$\endgroup$
  • 2
    $\begingroup$ My mind can only handle up to three. $\endgroup$ – Peter A. Schneider May 19 '17 at 8:30
  • $\begingroup$ So it is absolutely impossible that all chickens get picked? Why? $\endgroup$ – oerkelens May 22 '17 at 8:35
2
$\begingroup$

I thought of pairs. Only scenario where they're unpecked is if two chicks next to each other peck away from each other. 25% probability - either both to left, both to right, both away!, or both towards each other. Pretty much the same thing as above.

$\endgroup$
2
$\begingroup$

I shall solve the problem generally, let the total number of chicks be k, such that k > 3 (the reason behind this shall become apparent soon). Consider the set of all possible orientations of the chicks, essentially, all the different ways the chicks can peck each other. Let's focus our attention on one particular chick, say chick A. Consider all possible configurations of chicks if chick A and the two adjacent chicks to A were removed. Let the number of such configurations be n. For any one of these n configurations, we can construct four new configurations including the three previously removed chicks, three in which chick A is pecked, and one in which it isn't. Obviously, the total number of configurations of chicks is 4n. Now in all 4n configurations, chick A is pecked n times. This is true for any of the k chicks, so the total number of times a chick is pecked throughout all 4n configurations is kn. The expected value of the number of chicks pecked is the total number of times a chick is pecked divided by the total number of possible configurations, which is kn/4n = k/4.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.