IBM Ponder This #145 · May 2010

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.

Solution

Best opened after a real attempt

To be added.