# One hundred chicks peck a random neighbor. How many go unpecked? **URL:** \ **Category:** Factual Questions\ **Created:** [May 15, 2017, 11:03pm UTC](https://boards.straightdope.com/t/one-hundred-chicks-peck-a-random-neighbor-how-many-go-unpecked/786696 "2017-05-15T23:03:30Z")\ **Posts on this page:** 19\ **Page:** 2
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [May 21, 2017, 7:25pm UTC](https://boards.straightdope.com/t/one-hundred-chicks-peck-a-random-neighbor-how-many-go-unpecked/786696/21 "2017-05-21T19:25:39Z")
Consider 6 chickens total. The probability of 0 unpecked chickens is positive (it could be that every chicken pecks to their right, say), but the probability of 3 unpecked chickens is zero. So we do not have the symmetry merely for an even total number of chickens. What may be throwing you is that the number of unpecked chickens is closely related to the number of alternations… But they’re not the same. Rather, the number of unpecked chickens is the number of alternations that are not immediately followed by another alternation. (This is not entirely obvious; do you see why this is so?) One symmetry we do have for an even total number of chickens is that flipping every alternate chicken’s direction results in a new scenario with the same number of unpecked chickens. (This is not entirely obvious; do you see why this is so?). But this does not imply any symmetry on the probability distribution of the number of unpecked chickens. You are correct in your separate (contradictory?) statement that the right condition is that the total number of chickens n must be divisible by 4, and that the symmetry arises via flipping every alternate pair of chickens’ directions (in the sense of the cyclic pattern “keep the same, keep the same, flip, flip, keep, keep, flip, flip, etc.”), which takes scenarios with x unpecked chickens to scenarios with n/2 - x unpecked chickens (TINEO; DYSWTIS?), but I’m not sure how to reconcile this with the rest of your post or sure you see the reasoning for why this works. ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [May 21, 2017, 7:51pm UTC](https://boards.straightdope.com/t/one-hundred-chicks-peck-a-random-neighbor-how-many-go-unpecked/786696/22 "2017-05-21T19:51:13Z")
Ah, on re-read, I think maybe you do understand what’s going on, except for your mistaken last sentence about the situation where n is even. We get an unpecked chicken whenever we have an L followed by whatever followed by an R; that is, supposing an even total number of chickens and focusing on either of the two independent interlocking sets of every-other chicken (call these the two “every-other sets”), we get an unpecked chicken for each L directly followed by an R in either “every-other set”. The number of times an L to R transition happens within any circular set is of course half the total number of alternations within said set (there being an equal number of R to L transitions correspondingly). So, now supposing n divisible by four, so that each of these every-other sets is itself of even size, we can flip every other pair of chickens (which is to say, within each every-other set, flip every other chicken), so that the number of alternations within the two such sets go from x1 and x2 to n/2 - x1 and n/2 - x2, respectively, and thus the number of unpecked chickens goes from (x1 + x2)/2 to (n/2 - x1 + n/2 - x2)/2, which is to say, gets subtracted from n/2. This explains why the symmetry exists when n is divisible by 4, and a little further thought shows that the symmetry can’t be achieved when n is not divisible by 4 because it’s impossible to achieve n/2 unpecked chickens in such a case. ---
**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\ **Post date:** [May 21, 2017, 8:57pm UTC](https://boards.straightdope.com/t/one-hundred-chicks-peck-a-random-neighbor-how-many-go-unpecked/786696/23 "2017-05-21T20:57:19Z")
Thank you for elucidating my written-in-a-rush-and-therefore-borderline-incoherent statement. I had also worked out the exact probabilities for n=6, not to mention n=2, so I don’t know what was running through my mind when I wrote the last sentence. I think that with a bit of work we can just compute the probability distribution of the number of unpecked chicks as a function of n and x, but that may be pushing things beyond what one might expect from a kids’ problem. ---
**Author:** ![LSLGuy](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/lslguy/32/5813_2.png) [@LSLGuy](https://boards.straightdope.com/u/LSLGuy)\ **Post date:** [May 21, 2017, 9:04pm UTC](https://boards.straightdope.com/t/one-hundred-chicks-peck-a-random-neighbor-how-many-go-unpecked/786696/24 "2017-05-21T21:04:23Z")
If we want to keep playing … Leo’s OP has an incoherent third option that’s probably best analyzed as “Each of the n chickens is physically adjacent to all the other n-1 chickens. Each chicken pecks exactly one other chicken exactly one time at random. What’s the most likely number of unpecked chickens and can we say anything interesting about the probability distribution?” Clearly at this point the minimum number of peckees is one and the maximum is 100. Therefor the unpecked count ranges from 99 down to zero. It’s tempting to just arm-wave for 49.5. But I smell something more complex brewing. I hope it isn’t just the smell of chickenshit. 🙂 ---
**Author:** ![Chronos](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/chronos/32/134_2.png) [@Chronos](https://boards.straightdope.com/u/Chronos)\ **Post date:** [May 22, 2017, 12:32am UTC](https://boards.straightdope.com/t/one-hundred-chicks-peck-a-random-neighbor-how-many-go-unpecked/786696/25 "2017-05-22T00:32:59Z")
Well, the mean number of unpecked chickens in that case would be 100\*(98/99)^99. But I’m not sure what the mode would be. ---
**Author:** ![Channing\_Idaho\_Banks](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/channing_idaho_banks/32/250_2.png) [@Channing\_Idaho\_Banks](https://boards.straightdope.com/u/Channing_Idaho_Banks)\ **Post date:** [May 22, 2017, 12:50am UTC](https://boards.straightdope.com/t/one-hundred-chicks-peck-a-random-neighbor-how-many-go-unpecked/786696/26 "2017-05-22T00:50:19Z")
I think this is a trick question so I’m going with zero. ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [May 22, 2017, 6:38am UTC](https://boards.straightdope.com/t/one-hundred-chicks-peck-a-random-neighbor-how-many-go-unpecked/786696/27 "2017-05-22T06:38:48Z")
> [@DPRK](#): > > I think that with a bit of work we can just compute the probability distribution of the number of unpecked chicks as a function of n and x, but that may be pushing things beyond what one might expect from a kids’ problem. Yes, that’s right. Let n be the total number of chickens and x the number of unpecked chickens we are interested in. The probability of doing so will be the number of configurations which do so divided by 2^n. If n is odd and x is any integer, the number of configurations is (n choose 2x) \* 2. If n is even and x is odd, the number of configurations is ((n choose 2x) - (n/2 choose x)) \* 2. If n is even and x is even, the number of configurations is ((n choose 2x) + (n/2 choose x)) \* 2. Each of these clauses gives a function which has symmetry in replacing x by n/2 - x, but if n is odd, this transformation takes integer x to non-integer x (thus taking us out of the realm in which the first clause holds), and if n is even but not divisible by 4, this transformation changes the parity of x and thus which of the last two clauses applies. Only when n is divisible by 4 do we actually retain the apparent symmetry. ---
**Author:** ![Mijin](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/mijin/32/9369_2.png) [@Mijin](https://boards.straightdope.com/u/Mijin)\ **Post date:** [May 22, 2017, 7:35am UTC](https://boards.straightdope.com/t/one-hundred-chicks-peck-a-random-neighbor-how-many-go-unpecked/786696/28 "2017-05-22T07:35:09Z")
> [@Trinopus](#): > > What if they’re “all adjacent to all?” Every chick has a chance of pecking every other chick. (Maybe they all promenade past each other, and, at some random point, peck.) > > If I’m doing it right, the prob of not getting pecked is 49/50 ^ 50 – and that as the number of chicks rises, the limit of this prob turns to 1/e. > > If I’m not doing it right, never mind! I also thought about this scenario (I tried to guess what the question would be from the OP title) After basically brute forcing permutations, I think that the chance of _all_ the chickens being pecked is 1 / ((n - 1)^2) So, with 8 chickens for example the odds would be 1 / 7 ^ 2 = 1/49 ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [May 22, 2017, 7:56am UTC](https://boards.straightdope.com/t/one-hundred-chicks-peck-a-random-neighbor-how-many-go-unpecked/786696/29 "2017-05-22T07:56:16Z")
The chance of all chickens getting pecked should be n!/(n - 1)^n. There are (n - 1)^n equally likely possibilities overall (each of n chickens makes one of n - 1 choices of who to peck); we can think of these as all the functions from pecking chickens to corresponding victim chickens which have no fixed points. Out of these, the situations where ALL the chickens get pecked correspond to the case where these functions are surjective. A surjective function from a finite set to itself is the same as a permutation on that set, and there are n! many of those. ---
**Author:** ![Mijin](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/mijin/32/9369_2.png) [@Mijin](https://boards.straightdope.com/u/Mijin)\ **Post date:** [May 22, 2017, 8:35am UTC](https://boards.straightdope.com/t/one-hundred-chicks-peck-a-random-neighbor-how-many-go-unpecked/786696/30 "2017-05-22T08:35:42Z")
> [@Indistinguishable](#): > > The chance of all chickens getting pecked should be n!/(n - 1)^n. > > There are (n - 1)^n equally likely possibilities overall (each of n chickens makes one of n - 1 choices of who to peck); we can think of these as all the functions from pecking chickens to corresponding victim chickens which have no fixed points. > > Out of these, the situations where ALL the chickens get pecked correspond to the case where these functions are surjective. A surjective function from a finite set to itself is the same as a permutation on that set, and there are n! many of those. Clearly you have much more of a maths background than I have, but are you sure? Because for low values of n this function doesn’t seem to be delivering correct answers. 2 chickens = 2! / (2-1)^2 = 2 / 1^2 = 2 3 chickens = 3! / (3-1)^3 = 6 / 2^3 = 6/8 = 3/4 4 chickens = 4! / (4-1)^4 = 24 / (3^4) = 24/81 ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [May 22, 2017, 8:44am UTC](https://boards.straightdope.com/t/one-hundred-chicks-peck-a-random-neighbor-how-many-go-unpecked/786696/31 "2017-05-22T08:44:56Z")
Whoops, I should’ve used only the permutations with no fixed points! (I.e., “derangements”) Instead of n!, it should have been what is sometimes denoted !n. That is, the correct probability is n!/(n - 1)^n \* the correction factor of (1/0! - 1/1! + 1/2! - 1/3! + 1/4! … up through 1/n!). For large n, this correction factor is very nearly 1/e, and indeed, another way to put it is that the correct probability is 1/(n - 1)^n \* (the closest integer to n!/e), for positive n. ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [May 22, 2017, 8:55am UTC](https://boards.straightdope.com/t/one-hundred-chicks-peck-a-random-neighbor-how-many-go-unpecked/786696/32 "2017-05-22T08:55:29Z")
And, yes, as **Trinopus** noted, the mean number of unpecked chickens approaches n/e for large n (and is specifically n \* (1 - 1/(n - 1))^(n - 1), as **Chronos** noted). But this is separate from calculating the probability of zero unpecked chickens. ---
**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\ **Post date:** [May 22, 2017, 7:47pm UTC](https://boards.straightdope.com/t/one-hundred-chicks-peck-a-random-neighbor-how-many-go-unpecked/786696/33 "2017-05-22T19:47:45Z")
If you apply the “inclusion/exclusion principle” to count configurations, the number of possibilities with x unpecked chickens is: (n choose x) \* ∑ (-1)[sup]k[/sup] (n-x choose k) (n-x-k)[sup]x+k/sup[sup]n-x-k[/sup] where the sum goes from k=0 to n-x. (BTW note that the minimal number of peckees is 2, not 1. I am naturally assuming n\>1.) Now fix n and check which x makes it maximal. Also (not necessarily starting from the above expression), suppose n is large and derive a good approximation for the probability distribution, as in the case for derangements. ---
**Author:** ![Indistinguishable](https://avatars.discourse-cdn.com/v4/letter/i/90ced4/32.png) [@Indistinguishable](https://boards.straightdope.com/u/Indistinguishable)\ **Post date:** [May 22, 2017, 7:53pm UTC](https://boards.straightdope.com/t/one-hundred-chicks-peck-a-random-neighbor-how-many-go-unpecked/786696/34 "2017-05-22T19:53:46Z")
_ignore this post_ ---
**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\ **Post date:** [May 22, 2017, 10:51pm UTC](https://boards.straightdope.com/t/one-hundred-chicks-peck-a-random-neighbor-how-many-go-unpecked/786696/35 "2017-05-22T22:51:14Z")
Re. **LSLGuy** ’s first part, the most likely number should be close to n/e, but this requires careful proof (as in, feel free to use generating functions and some analysis)… unless there is some obvious symmetry or reduction of the problem I have overlooked (so probably yes) ---
**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\ **Post date:** [May 23, 2017, 6:09pm UTC](https://boards.straightdope.com/t/one-hundred-chicks-peck-a-random-neighbor-how-many-go-unpecked/786696/36 "2017-05-23T18:09:42Z")
Nobody? To be more explicit, here is one (incomplete) idea: For each n, construct a generating polynomial out of the number of unpecked chicks. That is, if U(n,m) is the number of configurations with n total and m unpecked chicks [NB “m” is what we called “x” above; I merely feel like using x for the variable], consider P(x) = ∑ U(n,m) x[sup]m[/sup]    (sum over m). For instance, when x=4, P(x) = 9 + 48x + 24 x[sup]2[/sup]. Since we know U(n,m) = ∑ (-1)[sup]l+m+n[/sup] (n choose m)(n-m choose l) l[sup]n-l/sup[sup]l[/sup]    (sum over l) by re-arranging the summation we can write P(x) = ∑ (-1)[sup]l+n[/sup] l[sup]n-l[/sup] (l-1)[sup]l[/sup] (n choose l) (1-x)[sup]n-l[/sup]    (sum over l) But now we can use a simple trick: suppose you verify that all the roots of P(x) are (negative) real numbers. In that case the degree with the maximum coefficient will be within 1 of P’(1)/P(1). The reason I want to do this is that P’(1) = n(n-1)(n-2)[sup]n-1[/sup] and P(1) = (n-1)[sup]n[/sup] so the most probable number of unpecked chicks will be within 1 of n(1 - 1/(n-1))[sup]n-1[/sup] (usually the integer ceiling of this, to be specific). Can someone complete/confirm/check any of this? Is it obvious that the mode is close to the mean? What continuous distribution are we approaching when n is large? ---
**Author:** ![DPRK](https://avatars.discourse-cdn.com/v4/letter/d/4491bb/32.png) [@DPRK](https://boards.straightdope.com/u/DPRK)\ **Post date:** [May 24, 2017, 4:10am UTC](https://boards.straightdope.com/t/one-hundred-chicks-peck-a-random-neighbor-how-many-go-unpecked/786696/37 "2017-05-24T04:10:18Z")
Sorry; please ignore most of that nonsense. There is no trick: the fact that the mode is close to the mean (aka P’(1)/P(1)) does indeed follow once we check that P(x) has real roots. Similarly we can compute the variance (aka P’’(1)/P(1) + P’(1)/P(1) - (P’(1)/P(1))^2 ) and then any real statistician would be able to say just how close the distribution approaches a normal or a Poisson distribution as n increases… So there is no unexpected shape. ---
**Author:** ![Itself](https://avatars.discourse-cdn.com/v4/letter/i/d07c76/32.png) [@Itself](https://boards.straightdope.com/u/Itself)\ **Post date:** [May 24, 2017, 5:30am UTC](https://boards.straightdope.com/t/one-hundred-chicks-peck-a-random-neighbor-how-many-go-unpecked/786696/38 "2017-05-24T05:30:05Z")
In short: Let X[SUB]i[/SUB] = 1 if chicken _i_ is pecked and 0 otherwise. Clearly each expectation value E[X[SUB]i[/SUB]] = 1/4; chicken _i_ is unpecked iff both chicken _i_ +1 and _i_ - 1 do not peck it, which are independent events each with probability 1/2. The expected number of chickens pecked is then E[X[SUB]1[/SUB] + … + X[SUB]100[/SUB]] = 100 E[X[SUB]1[/SUB]] = 25. For a line, it’s the same problem except for some edge effects that are fairly small as n -\> \infty. For an arbitrary configuration, the same sort of hoary linearity of expectation value argument applies if there’s some suitable symmetry to the configuration (e.g., the chickens are on the Cayley graph of some finite group, and each chicken chooses a neighbor to peck independently and uniformly at random). ---
**Author:** ![GiantRat](https://avatars.discourse-cdn.com/v4/letter/g/e47c2d/32.png) [@GiantRat](https://boards.straightdope.com/u/GiantRat)\ **Post date:** [May 24, 2017, 11:14am UTC](https://boards.straightdope.com/t/one-hundred-chicks-peck-a-random-neighbor-how-many-go-unpecked/786696/39 "2017-05-24T11:14:45Z")
This seems like a pretty direct derivation of the Birthday Paradox/Problem, which I’ll leave it to you to google (the betterexplained article is pretty good). Basically, if there are 75 people in a room, there is a 99.9% that two of them have the same birthday. I hate math, so my explanation would be confusing and possibly wrong. The Birthday Paradox is an important concept in things like cracking passwords, too, btw. [Previous page](https://boards.straightdope.com/t/one-hundred-chicks-peck-a-random-neighbor-how-many-go-unpecked/786696.md?page=1)