From: "G. A. Edgar" <edgar@math.ohio-state.edu.nospam>
Subject: Re: A coin tossing problem...
Date: Fri, 30 Apr 1999 11:11:25 -0400
Newsgroups: sci.math
Keywords: Mean of medians, order statistics

In article <ajw01.925433513@wumpus>, Andrew John Walker
<ajw01@uow.edu.au> wrote:

> Assume we have an unbiased two sided coin, one side heads the other tails.
> We repeatedly toss the coin and record how many throws are required
> for a head to appear. This sequence of numbers will have a mean of 2.
> 
> Now we take this sequence of numbers, group them into threes, and take
> the median of this group. This new sequence of numbers turn out to
> be quite interesting. It doesn't converge to an average of 2. In fact,
> computer trials suggest that it converges to 12/7. Prove or disprove
> this result.

I think you want to look into so-called "order statistics"... The
median of 3 numbers is the second-largest of them.

> 
> Similarly for a three sided coin or die, the medians appear to converge
> to 243/95. Here are the values I obtained up to 6 sides:
> 
>         Sides   Mean of 3 group median
>           2     12/7
>           3     243/95
>           4     880/259
>           5     775/183
>           6     5076/1001
> 
> I have determined an expression for the probability of the
> median being a given value, which I used to obtain a numerical
> value for the "mean of medians" and guess the above fractions.
> Can anyone obtain an exact value of "mean of medians" as a function
> of the number of sides?
> 
> I won't give the full working here, but if we let a=1/(number of sides)
> and n=value of median, then if M(n) is the probablity of n being
> the median we have
> 
> M(1)=(a^2)(3-2a)
> M(n)=3*(a^2) * (1-a)^(2n-2)-2*(a^3) * (1-a)^(3n-3)
>      +6a *(1-a)^(2n-1) * (1-[1-a]^[n-1])     n>1          
> 
> Good luck!
> --
> * Andrew Walker         *
> * Department Of Physics * e-mail -- ajw01@uow.edu.au
> * Wollongong University *
> * Australia             *
==============================================================================
[Remark: the 12/7 is correct. The probability that  n  tosses are necessary
 for a  head  to appear is  1/2^n. So we find the probability that the result
 of an experiment is
	=n, with probability  1/2^n
	>n, with probability  1/2^n  also  ( = sum(1/2^k, k>n) )
	<n, with probability  1 - 2(1/2^n)
 Now, the median will be  n  precisely in one of these mutually disjoint
 cases: one experiment requires   n  tosses, one fewer, one more;
	two experiments require   n  tosses, one fewer;
	two experiments require   n  tosses, one more;
	allthree experiments require   n  tosses
 These events occur, respectively, with probabilities
	(1/2^n)(1-2/2^n)(1/2^n)
	(1/2^n)^2(1-2/2^n)
	(1/2^n)^2(1/2^n)
	(1/2^n)^3
 for each selection of which of the three experiments will play each role;
 there are  6  ways to make the ordering in the first case, 3 in each of
 the next two, and only one in the last case. The weighted sum is
	9/(2^n)^2 - 14/(2^n)^3
 which one can check does sum to  1.

 Thus the expected value of the median is the sum of
	(  9/(2^n)^2 - 14/(2^n)^3  ) * n
 which is readily summed to be  12/7.   --djr]