Fwd: Number of swaps

[Deepak Jois]

This is an interesting point made by John Harvey about the number of swaps in the draw algorithm that is used by Tabbie.

John, you may want to consider joining the tabbie-devel mailing list at http://groups.google.com/group/tabbie-devel/members

Deepak

---------- Forwarded message ----------
From: John Harvey <jh...@cam.ac.uk>
Date: 10 Dec 2007 16:48:15 +0000
Subject: Re: Regarding the Random Number Seed
To: wudc...@googlegroups.com
Cc: Ciarán Lawlor < ciaran....@gmail.com >, Bob Nimmo <rn...@cam.ac.uk>


I think I will weigh in - I've been looking at these e-mail for a while now
and should probably get involved directly!

Firstly - Klaas, Deepak, I just wanted to say that I'm delighted that
someone has taken the initiative to get an open-source project going. There
have been a lot of tab programs with a lot of different pros and cons, and
I hope that something definitive (or close to it) will emerge from this. At
some stage in the future I hope I'll have the time to get involved rather
than shout (hopefully usefully) from the back seat.

My problem with point two is something like this. The rules require that,
within brackets, teams be placed in debates randomly. Tabbie starts from a
partially random allocation to debates (all pulled up teams being placed
together) and then shuffles teams around to make it random. The end result
will always have some remnant of the initial distribution, so the pulled up
teams will (always, I think, more thought required here!) be treated
slightly differently. The nature and magnitude of this depends on how many
swaps are carried out, and the more swaps carried out the smaller the
difference.

This isn't entirely satisfactory to my purist mind, and I would like to see
the teams in the brackets completely reordered before being allocated to
their debates. Then silverline could be run. I have some vague ideas on how
to efficiently do this within the architecture of the program, but I think
they're best left to the new year.

For the moment, we just need to be sure that there are enough swaps being
carried out so that we're as close to random as makes no difference. So -
you have 400 teams. If 5,000 swaps are attempted that means each team will
attempt a swap 25 times (on average). The worst case scenario is round 9:
there'll be about 20 brackets (less, but lets keep the numbers easy!). The
average bracket then holds 20 teams. We're not concerned with the
likelihood that a team is swapped with another on the same team points -
there'll still be clumping if that happens. Each swap attempted on a pulled
up team has a 5% chance of success of "declumping" the debate. That gives a
28% chance that the team is not swapped over the course of the 25 attempts.
Then that gives an 8% chance that two pulled up teams are not swapped and
left where they are. Of course, it could happen that the teams are both
swapped into the same debate. This is not a bad thing - this kind of
clumping should take place around 20% of the time. I think that 5,000 swaps
actually results in not enough clumping!

However, I'd like to see pulled-up teams being clumped together or not
clumped together in a more random way. It's not good enough that 28% of
pulled up teams won't be moved around within the bracket. With 20,000
attempted swaps this comes down to 0.6%, and the chances that a pair of
teams aren't swapped is negligible. So that would be better, I think. I
don't know what this means for programming efficiency - but I think it's
worth allowing the draw take its time.

Looking forward to your thoughts,

John.

On Dec 10 2007, Ciarán Lawlor wrote:

>
>2) My good friend John Harvey considers that the 5000 attempted swaps
>will yield a much lower number of actual swaps and so 5000 attempts
>might not be sufficient for this purpose. Without doing the precise
>maths on the issue, he feels that something closer to 20,000 attempts
>would be better. Of course if we've misunderstood and the tab
>actually carries out a guaranteed 5000 swaps attempting as many as
>possible until it has carried out 5000 then I think that might be ok
>- perhaps John might weigh in on this?
>

[Meir Maor]

I believe adding many many swap attempts for this purpose is very inefficent,
It would not be difficult to add a bracket randomization stage in
which all teams
in a bracket are randomized prior to the existing swapping attempts.
I could write this tomorow if deemed usefull, though I feel a need to
mention again
that I believe clumping pulled up teams actually makes a more fair
debate(analsys based on
standard deviation appeared in previous e-mail).

Me.

[Klaas van Schelven]

Hi Meir, others,

You have my blessing.... it's indeed a much nicer solution to do this right.

For concerned people - I'll take a look after Meir is finished, if Deepak does the same we still have three people looking at this before we use it at Worlds.

Klaas

p.s. Meir I agree with your theory that clustered pull ups are actually more fair and would love to build this in (or see you build it in) as an option after worlds.

[John Harvey]

Hi everybody,

 

I suspect that Meir is right on clustered pull ups being more fair, though haven't thought about it too far.

 

I'd be all for including it as an option, but I don't believe it can be considered to be in accordance with WUDC rules. The rules state that teams should be randomly allocated within their brackets, except with regard for positional allocation if desired. So for a WUDC tab we could never have a system where clustered pull ups were allowed, unless you could persuade council otherwise.

Good luck with getting these issues settled before Worlds, and happy to help at any stage,

 

John.