89
$\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$
3
  • 5
    $\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
    Commented May 16, 2017 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
    Commented May 18, 2017 at 22:27
  • $\begingroup$ See also Brian Hayes' blog, bit-player.org/2017/counting-your-chickens-before-theyre-pecked $\endgroup$
    – Gerry Myerson
    Commented Oct 12, 2017 at 8:33

11 Answers 11

Reset to default
221
$\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$
9
  • 177
    $\begingroup$ This answer is impeccable. $\endgroup$
    – Will Jagy
    Commented May 16, 2017 at 0:29
  • 29
    $\begingroup$ @WillJagy -- take your lousy upvote, you animal. $\endgroup$
    – Michael Lorton
    Commented May 16, 2017 at 2:37
  • 4
    $\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
    Commented May 17, 2017 at 7:31
  • 2
    $\begingroup$ ......., qui tollis peccata mundi, miserere nobis. $\endgroup$
    – Will Jagy
    Commented May 17, 2017 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
    Commented May 18, 2017 at 22:25
19
$\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$
20
  • 7
    $\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
    Commented May 17, 2017 at 7:47
  • 3
    $\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$
    – Caleb Stanford
    Commented May 18, 2017 at 1:58
  • 4
    $\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
    Commented May 19, 2017 at 2:21
  • 3
    $\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
    Commented May 19, 2017 at 14:01
  • 3
    $\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$
    – hmakholm left over Monica
    Commented May 19, 2017 at 16:15
11
$\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$
8
$\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$
11
  • 1
    $\begingroup$ chicks, not children $\endgroup$
    – Marc van Leeuwen
    Commented May 17, 2017 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
    Commented May 17, 2017 at 13:19
  • 1
    $\begingroup$ Great alternate answer, although the fact it only applies if $4 \mid n$ does diminish it slightly. $\endgroup$
    – Caleb Stanford
    Commented May 19, 2017 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$
    – Caleb Stanford
    Commented Jun 9, 2017 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$
    – Caleb Stanford
    Commented Jun 9, 2017 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$
3
  • $\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
    Commented May 15, 2017 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
    Commented May 17, 2017 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
    Commented May 17, 2017 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$
2
  • 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
    Commented May 17, 2017 at 7:26
  • 1
    $\begingroup$ @MarcvanLeeuwen If this were homework, I'd agree with you. $\endgroup$
    – Fabio Somenzi
    Commented May 17, 2017 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
  • 2
    $\begingroup$ My mind can only handle up to three. $\endgroup$
    – Peter - Reinstate Monica
    Commented May 19, 2017 at 8:30
  • $\begingroup$ So it is absolutely impossible that all chickens get picked? Why? $\endgroup$
    – oerkelens
    Commented May 22, 2017 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 not pecked n times. This is true for any of the k chicks, so the total number of times a chick is not pecked throughout all 4n configurations is kn. The expected value of the number of chicks not pecked is the total number of chicks that are unpecked divided by the total number of possible configurations, which is kn/4n = k/4.

$\endgroup$
0
$\begingroup$

Represent chickens as variables ($a_{1}, a_{2}, \dots, a_{100})$. Assign it a $1$ if unpecked, $0$ otherwise. We want to find the expected value of the sum $a_{1} + \dots + a_{100}$. Notice that the expected value of each of these is $\frac{1}{4}$, so by linearity of expectation, the expected value of the sum is $100 \cdot \frac{1}{4} = 25$

$\endgroup$
0
$\begingroup$

I suspect the original answer to the competition question is not correct. I am not a mathematician and I apologize if I am wrong. Putting aside "how does the chick feel about pecking left and right" because it's completely random as stated, there are in total 6 possible sets of outcome, 4 that were mentioned and 2 additional ones. The last 2 sets represent another "chance" or another possible set of outcomes. The problem here is that we have 100 chicks and not 4.

  1. all chicks peck to the left. 0% of chicks are unpecked.
  2. all chicks peck to the right. 0% of chicks are unpecked.
  3. all chicks, divided in pairs, peck each other, 0% of chicks are unpecked.
  4. chicks are divided in groups of 4, where the pair in the middle pecks each other, while chicks on the edge peck this pair in the middle. 50% of chicks are unpecked.

There are however other possible probability distributions. Two new patterns emerge from this.

  1. chicks are divided into groups of 3, where a pair of chicks pecks each other and one chick from this pair is double pecked by a chick on the LEFT. This chick on the left is unpecked which makes a total of 33%. The last, 100th chick can peck randomly left or right but remains unpecked itself as in example 4). This gives 34 unpecked chicks.
  2. chicks are divided into groups of 3, where a pair of chicks pecks each other and one chick from this pair is double pecked by a chick on the RIGHT. The last, 100th chick can peck randomly left or right but remains unpecked itself as in example 4). This gives 34 unpecked chicks.

A mixture of all those sets of outcomes are, of course, also possible. Now we can calculate the median of these 6 possible outcomes: (0+0+0+50+34+34)/6=19.666 somewhat lower than the original solution.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .