Behdad Esfahbod's daily notes on GNOME, Pango, Fedora, Persian Computing, Bob Dylan, and Dan Bern!

Archives

July 2003

August 2003

October 2003

November 2003

December 2003

March 2004

April 2004

May 2004

July 2004

August 2004

September 2004

November 2004

March 2005

April 2005

May 2005

June 2005

July 2005

August 2005

September 2005

October 2005

November 2005

December 2005

January 2006

February 2006

March 2006

April 2006

May 2006

June 2006

July 2006

August 2006

September 2006

October 2006

November 2006

December 2006

January 2007

February 2007

March 2007

April 2007

May 2007

June 2007

July 2007

August 2007

September 2007

October 2007

November 2007

December 2007

January 2008

February 2008

March 2008

April 2008

May 2008

June 2008

July 2008

August 2008

October 2008

November 2008

December 2008

January 2009

March 2009

April 2009

May 2009

June 2009

July 2009

August 2009

November 2009

December 2009

March 2010

April 2010

May 2010

June 2010

July 2010

October 2010

November 2010

April 2011

May 2011

August 2011

September 2011

October 2011

November 2011

November 2012

June 2013

January 2014

May 2015

Current Posts

July 2003

August 2003

October 2003

November 2003

December 2003

March 2004

April 2004

May 2004

July 2004

August 2004

September 2004

November 2004

March 2005

April 2005

May 2005

June 2005

July 2005

August 2005

September 2005

October 2005

November 2005

December 2005

January 2006

February 2006

March 2006

April 2006

May 2006

June 2006

July 2006

August 2006

September 2006

October 2006

November 2006

December 2006

January 2007

February 2007

March 2007

April 2007

May 2007

June 2007

July 2007

August 2007

September 2007

October 2007

November 2007

December 2007

January 2008

February 2008

March 2008

April 2008

May 2008

June 2008

July 2008

August 2008

October 2008

November 2008

December 2008

January 2009

March 2009

April 2009

May 2009

June 2009

July 2009

August 2009

November 2009

December 2009

March 2010

April 2010

May 2010

June 2010

July 2010

October 2010

November 2010

April 2011

May 2011

August 2011

September 2011

October 2011

November 2011

November 2012

June 2013

January 2014

May 2015

Current Posts

Saturday, June 02, 2007

PUZZLE SOLUTION: Group Strategy
This is the solution to the puzzle Group Strategy that I posted a few weeks ago. Make sure you give it a try before reading further.

**Intro:**

There are multiple ways one can approach the solution. Some need more combinatorial background than the others. One intuitive way that Carl Worth suggested was: what should the strategy look like if we want to make sure that the identity permutation always leads to success? Easy, each man should make sure to look into the box numbered as himself. Now what if the permutation is not identity, but identity plus one swap? Continue...

Another approach is probabilistic. Any strategy that has each man's rate of success in finding his number be probabilistically independent of the others is destined to fail with a total success rate of at most 2^-2k. So, in any winning strategy, the success rate of the men are not independent. A corollary is that no man should know which boxes he's going to open until after he entered the room. Think about it (and no, don't think about random strategies).

**Strategy:**

So here is the winning strategy: Each man enters the room, opens the box numbered as himself and reads the paper inside; while not found, he then opens the box with the number written on piece of paper in the last box he opened.

Of course, every man still has the exact same rate of individual success: 1/2, but what the algorithm does is to kinda "align" their success runs together so as a group they succeed with a surprisingly huge probability: more than 30%!

**Proof:**

The algorithm becomes a lot more intuitive if one imagines the graph representation of the permutation that the boxes represent. The graph representation of our permutation has 2k nodes, and node i has an edge towards node j if number j is in box i. This is a directed graph.

Permutation graphs are always a set of (possibly size 1) cycles because each node has in and out degrees of exactly one. The man numbered i wants to find the node that has an outgoing edge to i. Well, looking at the problem this way, the strategy is trivial: start from node i and follow the cycle, until you get back to i. That's all everyone has got to do!

The success probability of the group is equal to the probability that the permutation graph has no cycle longer than k. And since there are only 2k nodes and each node is in exactly one cycle, there can exist at most one cycle longer than k. The question is: what is the probability that a cycle longer than k exists. This is the failure probability.

Getting this far you can claim having solved the puzzle! Now to get a tight bound: I used straight counting. Failure probability is the sum of probability that a cycle of size c exists, for c from k+1 to 2k. The probability that such a cycle exists is the number of permutations with such a cycle divided by total number of permutations (2k!). Finally lets count how many such permutations exist: Choose c members for the cycle and divide by c because the order is not important: 2k! / ((2k-c)! * c). Finally permute the remaining members: (2k-c)!. It simplifies drastically and at the end, failure probability becomes exactly H(2k) - H(k), where H(n) is the n'th Harmonic number. A tight upper bound to this failure probability is ln(2k) - ln(k), which is ln(2). So, success probability is not less than 1 - ln(2), which is a bit over 30%.

The math set using my embedded TeX engine (click for other sizes):

There are multiple ways one can approach the solution. Some need more combinatorial background than the others. One intuitive way that Carl Worth suggested was: what should the strategy look like if we want to make sure that the identity permutation always leads to success? Easy, each man should make sure to look into the box numbered as himself. Now what if the permutation is not identity, but identity plus one swap? Continue...

Another approach is probabilistic. Any strategy that has each man's rate of success in finding his number be probabilistically independent of the others is destined to fail with a total success rate of at most 2^-2k. So, in any winning strategy, the success rate of the men are not independent. A corollary is that no man should know which boxes he's going to open until after he entered the room. Think about it (and no, don't think about random strategies).

So here is the winning strategy: Each man enters the room, opens the box numbered as himself and reads the paper inside; while not found, he then opens the box with the number written on piece of paper in the last box he opened.

Of course, every man still has the exact same rate of individual success: 1/2, but what the algorithm does is to kinda "align" their success runs together so as a group they succeed with a surprisingly huge probability: more than 30%!

The algorithm becomes a lot more intuitive if one imagines the graph representation of the permutation that the boxes represent. The graph representation of our permutation has 2k nodes, and node i has an edge towards node j if number j is in box i. This is a directed graph.

Permutation graphs are always a set of (possibly size 1) cycles because each node has in and out degrees of exactly one. The man numbered i wants to find the node that has an outgoing edge to i. Well, looking at the problem this way, the strategy is trivial: start from node i and follow the cycle, until you get back to i. That's all everyone has got to do!

The success probability of the group is equal to the probability that the permutation graph has no cycle longer than k. And since there are only 2k nodes and each node is in exactly one cycle, there can exist at most one cycle longer than k. The question is: what is the probability that a cycle longer than k exists. This is the failure probability.

Getting this far you can claim having solved the puzzle! Now to get a tight bound: I used straight counting. Failure probability is the sum of probability that a cycle of size c exists, for c from k+1 to 2k. The probability that such a cycle exists is the number of permutations with such a cycle divided by total number of permutations (2k!). Finally lets count how many such permutations exist: Choose c members for the cycle and divide by c because the order is not important: 2k! / ((2k-c)! * c). Finally permute the remaining members: (2k-c)!. It simplifies drastically and at the end, failure probability becomes exactly H(2k) - H(k), where H(n) is the n'th Harmonic number. A tight upper bound to this failure probability is ln(2k) - ln(k), which is ln(2). So, success probability is not less than 1 - ln(2), which is a bit over 30%.

The math set using my embedded TeX engine (click for other sizes):

**Update:**

Proof that the bound is tight: While failure probability is not more than ln(2k) - ln(k), using the same idea, it's not less than ln(2k+1) - ln(k+1). So, success probability is between 1 - ln(2) and 1 - ln(2 - 1/(k+1)).

Comments:

Links to this post:

<< Archive

<< Home

Your strategy as described doesn't seem optimal. Consider a 4-player game, with 4 boxes, where boxes 1,2,3,4 contain the number 4,1,3,2. This is a loser because there is a permutation group of length 3. But as you describe it, a player who picks box 3, which contains 3, will loop forever, while picking another box at random will increase his probability of success.

But it doesn't affect the probability of winning in the limit, since the players are reduced to guessing at random.

Post a Comment
But it doesn't affect the probability of winning in the limit, since the players are reduced to guessing at random.

Links to this post:

<< Archive

<< Home