Ponder This Challenge - May 2010 - Quantization of probability vector

Ponder This Challenge:

The idea for this month's challenge came from a presentation given by Ohad Rodeh. Let P = {p_i}_{i=0}^9 be a probability distribution over the digits (\sum_{i=0}^9 p_i = 1). There are infinitely many possibilities for P.

A common way to make this number finite is to quantize each p_i into, say, four different bins. The obvious way to do this is as follows: 0<=x<0.25; 0.25<=x<0.5; 0.5<=x<0.75; and 0.75<=x<=1.

A. How many, out of the 4^10=1,048,576 possibilities, can be realized by a probability vector?
B. If we change the boundaries of the four bins, what is the maximum number of possibilities that can be realized?

Update: May 6th: To those of you who do not master TeX notation, P is a vector of ten non-negative real numbers (p0,p1,p2,...,p9) and their sum (p0+p1+p2+...+p9) is 1.

Update: May 6th: In part B you can change the boundaries of the intervals, but they must be disjoint: [0,A) [A,B) [B,C) and [C,1] for 0<A<B<C<1.

Update: May 9th: For example, if P=(0.01,0.02,0.04,0.03,0.1,0.51,0.01,0.01,0.26,0.01) then the quantized version, according to part A, is (a,a,a,a,a,c,a,a,b,a); and for part B, if we change the boundaries (for example) to a=[0,0.05); b=[0.05,0.15); c=[0.15,0.44); d=[0.44,1] we get (a,a,a,a,b,d,a,a,c,a). (d,d,d,d,d,d,d,d,d,d) is not realizeable since there is no probability vector with all 10 elements greater than 0.44.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  Part A:
  We number the bins from the first bin, [0,0.25), as bin #0; and the last bin [0.75,1], as bin #3. A 10-tuple of 4-bins (b1,b2,...,b10) is realizable if and only if b1+b2+...+b10 <= 4. There is a one-to-one mapping of 10 non-negative integers whose sum is no more than 4, with an arrangement of 10 balls and 4 bars. Out of the (14 \choose 4) such arrangements, 10 are illegal (we have 0,1,2,3 so we cannot use 4). The answer is therefore 1001-10=991.

  Part B:
  If we take any realizable quantization and shift every probability D bins to the left (or right), it is easy to see that we get a non-realizable quantization. Therefore, there are at least 3^10 unrealizable quantization since all the ones with an empty first bin are either unrealizable, or at least one shift of them is. This bound is tight since, for example, [0,0.01) [0.01,0.02) [0.03 0.04) [0.04 1] achieves it by realizing exactly 4^10-3^10=989527 possibilities.

Solvers

• John T. Robinson (04/30/2010 11:53 PM EDT)
• (04/30/2010 11:53 PM EDT)
• Joseph DeVincentis (05/01/2010 12:41 AM EDT)
• (05/01/2010 12:41 AM EDT)
• Michael Liepelt (05/01/2010 08:38 AM EDT)
• (05/01/2010 08:38 AM EDT)
• Pataki Gergely (05/01/2010 12:02 PM EDT)
• (05/01/2010 12:02 PM EDT)
• Amos Guler (05/02/2010 03:47 PM EDT)
• (05/02/2010 03:47 PM EDT)
• Arthur Breitman (05/03/2010 03:07 PM EDT)
• (05/03/2010 03:07 PM EDT)
• Dan C (05/03/2010 12:24 PM EDT)
• olestock (05/03/2010 12:24 PM EDT)
• (05/03/2010 12:24 PM EDT)
• Michael Brand (05/04/2010 07:05 AM EDT)
• Don Dodson & David Dodson (05/04/2010 05:28 PM EDT)
• (05/04/2010 05:28 PM EDT)
• Tom Sirgedas (05/04/2010 06:34 PM EDT)
• (05/04/2010 06:34 PM EDT)
• Viacheslav Chernoy (05/04/2010 09:17 PM EDT)
• (05/04/2010 09:17 PM EDT)
• Dmitry Litvinenko (05/05/2010 01:59 PM EDT)
• (05/05/2010 01:59 PM EDT)
• Adam Daire (05/05/2010 07:05 PM EDT)
• (05/05/2010 07:05 PM EDT)
• Artiom Myaskouvskey (05/06/2010 03:57 AM EDT)
• (05/06/2010 03:57 AM EDT)
• Austin Shapiro (05/06/2010 11:43 AM EDT)
• Chuck Grant (05/06/2010 12:04 PM EDT)
• Mark Mixer (05/06/2010 03:12 PM EDT)
• Motty Porat (05/06/2010 06:10 PM EDT)
• Jonathan Campbell (05/06/2010 06:25 PM EDT)
• John Ritson (05/06/2010 08:23 PM EDT)
• Ross Millikan (05/06/2010 09:40 PM EDT)
• Clive Tong (05/08/2010 05:14 AM EDT)
• Sevag Papazian (05/08/2010 07:11 AM EDT)
• Thomas Jessen (05/08/2010 11:30 AM EDT)
• Albert Stadler (05/09/2010 05:41 AM EDT)
• Daniel Bitin (05/09/2010 08:17 AM EDT)
• Nicolas Landes (05/09/2010 02:39 PM EDT)
• Dan Ignatoff (05/09/2010 07:07 PM EDT)
• David Friedman (05/10/2010 02:05 PM EDT)
• Dan Dima (05/10/2010 06:46 PM EDT)
• Danny Antonetti (05/10/2010 09:42 PM EDT)
• Phil Benamy (05/11/2010 01:41 AM EDT)
• Ari Freund (05/11/2010 03:21 AM EDT)
• Andreas Stiller (05/11/2010 08:46 PM EDT)
• Serge Thill (05/12/2010 05:43 PM EDT)
• Christian Blatter (05/14/2010 04:29 AM EDT)
• Lachezar Hristov (05/14/2010 04:34 AM EDT)
• J (05/14/2010 10:53 AM EDT)
• onathan A Wildstrom (05/14/2010 10:53 AM EDT)
• Harald Bögeholz (05/15/2010 12:10 PM EDT)
• Don Ryan (05/17/2010 02:48 AM EDT)
• Venkata Ramayya (05/17/2010 07:24 AM EDT)
• Sylvain Becker (05/17/2010 06:16 PM EDT)
• Jan Fricke (05/18/2010 01:26 PM EDT)
• Abhishek Jha (05/21/2010 05:30 PM EDT)
• Anoop Varghese (05/22/2010 01:09 PM EDT)
• William Heller (05/23/2010 10:24 AM EDT)
• Sidharth Lath (05/23/2010 10:58 AM EDT)
• Varun Jindal IIT Kanpur (05/25/2010 01:39 PM EDT)
• Fabio Filatrella (05/25/2010 02:13 PM EDT)
• Nagy Zoltan (05/25/2010 02:58 PM EDT)
• Adel El-Atawy (05/26/2010 02:25 PM EDT)
• Khalid Elbadawi (05/28/2010 10:29 PM EDT)
• Matthew Paterson (05/30/2010 01:59 PM EDT)
• John G Fletcher (05/30/2010 06:03 PM EDT)
• Adriana Clerici (05/31/2010 11:16 AM EDT)
• Se Kwon Kim (05/31/2010 08:01 PM EDT)
• Nyles Heise (05/31/2010 09:41 PM EDT)