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.
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.
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.
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.
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.
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.
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.
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.
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.
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)
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].
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?
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.
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).
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.
