Probability puzzler

[Xcott Craver]

I use this problem as an example every year in class. I will post the
answer tomorrow.

A large number (N) of students and one (1) professor stand in a long
line, in randomized order---with every permutation of people equally
likely to occur. Everyone to the professor's left is "team A";
everyone to the professor's right is "team B." What is the expected
size of a student's team?


==
"Taking jokes seriously is the exact mirror activity of laughing if
someone says they have cancer." --jbou ,

[John Dawkins]

In article <mtf12h$bp2$1...@dont-email.me>,

Xcott Craver <nos...@nospam.invalid> wrote:

> I use this problem as an example every year in class. I will post the
> answer tomorrow.
>
> A large number (N) of students and one (1) professor stand in a long
> line, in randomized order---with every permutation of people equally
> likely to occur. Everyone to the professor's left is "team A";
> everyone to the professor's right is "team B." What is the expected
> size of a student's team?

(2N+1)/3, which is equal to 1+(2/3)(N-1).

Let us call our student Gosset. For each of the other students in the
class, that student will be on the same team as Gosset if and only if
the Professor doesn't end up between them in the line, and this will
happen for 2/3 of the permutations. This explains the (2/3)(N-1) above.
The 1 in front is Gosset himself.
--
J.

[Bill]

Xcott Craver wrote:
> I use this problem as an example every year in class. I will post the
> answer tomorrow.
>
> A large number (N) of students and one (1) professor stand in a long
> line, in randomized order---with every permutation of people equally
> likely to occur. Everyone to the professor's left is "team A";
> everyone to the professor's right is "team B." What is the expected
> size of a student's team?

Since each student is equally likely to be on one side of the professor
(or the other), and these should have the same expected size, I say
N/2. Your question worries me that I am overlooking something! :)

Bill

[Bill]

Bill wrote:
> Xcott Craver wrote:
>> I use this problem as an example every year in class. I will post
>> the answer tomorrow.
>>
>> A large number (N) of students and one (1) professor stand in a long
>> line, in randomized order---with every permutation of people equally
>> likely to occur. Everyone to the professor's left is "team A";
>> everyone to the professor's right is "team B." What is the expected
>> size of a student's team?
> Since each student is equally likely to be on one side of the
> professor (or the other), and these should have the same expected
> size, I say N/2. Your question worries me that I am overlooking
> something! :)
>

I read the question again and see how the error of my ways. The
possibility that Team A has 1 member and Team B and N-1 members merits
a higher probability than I have assigned it, etc.

[William Elliot]

On Thu, 17 Sep 2015, Xcott Craver wrote:

> A large number (N) of students and one (1) professor stand in a long line,
> in randomized order---with every permutation of people equally likely to
> occur.

> Everyone to the professor's left is "team A"; everyone to the professor's
> right is "team B." What is the expected size of a student's team?

There are n+1 positions for the professor. Expected number of students
for team A is (0 + 1 +..+ n)/(n + 1) = n(n + 1)/2(n + 1) = n/2.
Likewise team B.

[David Petry]

On Thursday, September 17, 2015 at 4:08:35 PM UTC-7, John Dawkins wrote:
> In article <mtf12h$bp2$1...@dont-email.me>,
> Xcott Craver <nos...@nospam.invalid> wrote:
>
> > I use this problem as an example every year in class. I will post the
> > answer tomorrow.
> >
> > A large number (N) of students and one (1) professor stand in a long
> > line, in randomized order---with every permutation of people equally
> > likely to occur. Everyone to the professor's left is "team A";
> > everyone to the professor's right is "team B." What is the expected
> > size of a student's team?

Some respondents in this thread are confusing "expected size of a student's team", with "expected size of a team of students".

> (2N+1)/3, which is equal to 1+(2/3)(N-1).

That's funny. I got 2/(N^2+N)*sum(k=0..N) k^2

> Let us call our student Gosset.

Can I call him Bill?

> For each of the other students in the
> class, that student will be on the same team as Gosset if and only if
> the Professor doesn't end up between them in the line, and this will
> happen for 2/3 of the permutations. This explains the (2/3)(N-1) above.
> The 1 in front is Gosset himself.

I think that's a very clever argument. And correct. But, can you come up with another probability problem that uses the same kind of reasoning? Is there a general principle or method that I'm missing?

[Jussi Piitulainen]

Xcott Craver writes:

> I use this problem as an example every year in class. I will post the
> answer tomorrow.
>
> A large number (N) of students and one (1) professor stand in a long
> line, in randomized order---with every permutation of people equally
> likely to occur. Everyone to the professor's left is "team A";
> everyone to the professor's right is "team B." What is the expected
> size of a student's team?

(2 * N + 1) / 3, also for small N.

[Bill]

You are assuming "all outcomes" (regarding sizes) are equally-likely. I
believe you need to sum with appropriate weights.

[Jussi Piitulainen]

Xcott Craver writes:

> I use this problem as an example every year in class. I will post the
> answer tomorrow.
>
> A large number (N) of students and one (1) professor stand in a long
> line, in randomized order---with every permutation of people equally
> likely to occur. Everyone to the professor's left is "team A";
> everyone to the professor's right is "team B." What is the expected
> size of a student's team?

Was I supposed to give my reasoning?

I decided that the specification of a large N was a herring, played with
small cases to convince myself that the order of the other students
doesn't matter, left or right doesn't matter, but the position of the
specific student in their team does. So there're k ways to be in a team
of size k, for k = 1, ..., N. (Also 0 ways to be in a team of size 0.)

That gave P(size = k) = k/((N + 1)/2), which do not add to 1, and it
took a while to notice and correct my stupid mistake.

After the correction, I set E(size) = sum(P(size = k) * k), and used
Method 0 of Graham, Knuth, and Patashnik to simplify the sum. (Method 0
is to look it up.)

I also tested the solution by programming the full combinatorics (all
permutations, not ignoring anything) and seeing that the proportion of
k-sized teams agrees with the probability, and mean size agrees with the
expectation. Which they do. This can only be done for quite small N.

Very nice problem.

[Ross A. Finlayson]

Pairwise half are on the same side
but also half are on the other side.

That is to say, for a sample, there
are all the other samples that only
fill the rest of the space and are
never duplicates, the population.
Sampling always goes to the mean.
This is not stochastic where the
distribution of samples (eg bits) is
normal and ergodic (unbounded).
Instead, out of the entire space of
"solutions", there is each one, though
it is combinatorially large, when the
order is read out, half of those have
a given student before the teacher,
half after (sampling the entire population).
Of those, a student could expect half
before and half after, or the middle (as
at least a local maxima of expectation).

[duncan smith]

If we have n students to the left of the professor, then the expected
size of a student's team is,

(n^2 + (N-n)^2) / N

Averaging over the possible positions for the professor we get,

sum from n=0 to N {(n^2 + (N-n)^2) / N} / (N+1)

= (2/N/(N+1)) sum from n=0 to N {n^2}

For large N we can approximate the sum with the corresponding integral
and, as N/(N+1) is close to 1, I get approx.,

(2/3)N

Duncan

[John Dawkins]

In article <6013f6f4-d822-4e6a...@googlegroups.com>,

The general principle in use here is the Method of Indicators. The
number of students on Bill Gosset's team is

1 + sum_{i = 2,3,...,N} I_{A_i}

where A_i is the event that student i is on Gosset's team. As noted
E(1_{A_i}) = P(A_i) = 2/3 for each i. The expected number on Gosset's
team is therefore

1 + sum_{i = 1,2,...,N} (2/3) = 1 + (N-1)(2/3).
--
J.

[Xcott Craver]

On 2015-09-17 23:08:26 +0000, John Dawkins said:

>
> (2N+1)/3, which is equal to 1+(2/3)(N-1).
>
> Let us call our student Gosset. For each of the other students in the
> class, that student will be on the same team as Gosset if and only if
> the Professor doesn't end up between them in the line, and this will
> happen for 2/3 of the permutations.

Your argument is correct, but just out of curiousity: how do you conclude that
2/3 of the permutations have Gosset and friend on the same side as the
professor?

[Xcott Craver]

On 2015-09-17 18:35:47 +0000, Xcott Craver said:

> I use this problem as an example every year in class. I will post the
> answer tomorrow.

Lots of people got this right: the answer is indeed (2N+1)/3.

The expected size of team A is N/2, since the professor falls in every
location with equal likelihood, and hence every team size has equal
likelihood. This is also true for team B, and therefore (N/2) is the
expected size of either team. It may therefore seem that the expected
size of a student's team is (N/2) regardless of how the student is
assigned.

However, we know that the "size of a student's team" cannot be zero,
because it is a student's team. Therefore this must have a different
distribution than the "size of team A". Conditionally we have, for a
student s who learns that he or she is assigned to team A:

Pr[ size(A)=k | s \in A ] = Pr[ s \in A | size(A)=k ] Pr[ size(A)=k ] /
Pr[ s \in A ]
= ( k/N ) ( 1/(N+1) ) / ( 1/2 )
= k * 2/(N*(N+1))

This has a ramp distribution rather than a flat uniform distribution,
so not only is size 0 impossible, but large team sizes have
significantly inflated probability. The same logic applies to any team
assignment, so the student knows this distribution *before* assignment.

This gives an expected value of [sum] k^2 * 2/(N*(N+1)) = (2/6)
(2N+1)N(N+1) / (N(N+1)).

I call this the "Groucho Marx Paradox," because Groucho Marx joked that
he would never join a club who would have him as a member. Here we see
a mathematical basis for that opinion: if I choose a random club with
a random(*) size, and then you learn that you are a member,
conditionally you can conclude that the club was far less exclusive
than you previously thought.

(*) With the right distribution, for example a uniform one.

[David Petry]

On Friday, September 18, 2015 at 11:08:45 AM UTC-7, Xcott Craver wrote:
> On 2015-09-17 23:08:26 +0000, John Dawkins said:
>
> >
> > (2N+1)/3, which is equal to 1+(2/3)(N-1).
> >
> > Let us call our student Gosset. For each of the other students in the
> > class, that student will be on the same team as Gosset if and only if
> > the Professor doesn't end up between them in the line, and this will
> > happen for 2/3 of the permutations.
>
> Your argument is correct, but just out of curiousity: how do you conclude that
> 2/3 of the permutations have Gosset and friend on the same side as the
> professor?

Students A,G, and professor P.

There are six permutations

PAG PGA APG GPA AGP GAP

and four of the six have two students on the same side.

> "Taking jokes seriously is the exact mirror activity of laughing if
> someone says they have cancer." --jbou

That's, um, like, NOT FUNNY!


:-)

[John Dawkins]

In article <999029ed-f609-43cd...@googlegroups.com>,

David Petry <david...@gmail.com> wrote:

> On Friday, September 18, 2015 at 11:08:45 AM UTC-7, Xcott Craver wrote:
> > On 2015-09-17 23:08:26 +0000, John Dawkins said:
> >
> > >
> > > (2N+1)/3, which is equal to 1+(2/3)(N-1).
> > >
> > > Let us call our student Gosset. For each of the other students in the
> > > class, that student will be on the same team as Gosset if and only if
> > > the Professor doesn't end up between them in the line, and this will
> > > happen for 2/3 of the permutations.
> >
> > Your argument is correct, but just out of curiousity: how do you conclude
> > that
> > 2/3 of the permutations have Gosset and friend on the same side as the
> > professor?
>
> Students A,G, and professor P.
>
> There are six permutations
>
> PAG PGA APG GPA AGP GAP
>
> and four of the six have two students on the same side.
>

Precisely.
--
J.

[Ross A. Finlayson]

This is where

x^hat

or

x^ <= 1/2
x^ >= 1/3.

What is the best way
to read through an
ordering and establish
the sample value?

Here "best" is in terms
of computational resources.