# A question about the size of a L1 ball

I met with a problem when I am reading a paper "On the Redundancy of Slepian-Wolf Coding" by He, DK; Lastras-Montano, LA; Yang, EH; Jagmohan, A; Chen, J, IEEE TRANSACTIONS ON INFORMATION THEORY, ISSN 0018-9448, 12/2009, Volume 55, Issue 12, pp. 5607 - 5627. The image below is an excerption of the paper where I have a question.

Here the term "type" just means pmf on $\mathcal{X}\times\mathcal{Y}$ with each entry having denominater $n$. We can think of it as a result produced by the following process: assume I have $n$ coins and want to place them on a chessboard having $|\mathcal{X}|\times|\mathcal{Y}|$ squares. After placing the coins, each square of the chessboard has $0..n$ coins and the sum of numbers of coin(s) in all squares is $n$. the type is defined to be a sequence(or matrix) of size $|\mathcal{X}|\times|\mathcal{Y}|$ with each element being the number of coins in the corresponding square devided by $n$. We can see that type is actually a pmf on $\mathcal{X}\times\mathcal{Y}$ but the denominator of each probability is $n$ (if not reduced). All of the types on $\mathcal{X}\times\mathcal{Y}$ is denoted as $\mathcal{T}_n(\mathcal{X}\times\mathcal{Y})$.

In the paper, $s$ and $s^\*$ are all types on $\mathcal{X}\times\mathcal{Y}$. $s^\*$ is a given fixed type; we can consider it as a constant. $s_\mathcal{X}$ means the marginal pmf on $\mathcal{X}$ (recall that $s$ is a pmf). It is required that $s_\mathcal{X}$ is a given fixed $t$. $s^\*_\mathcal{X}$ is also required by the lemma mentioned to be $t$. $\kappa$ is an arbitrary positive real number. $\tau(x^n,y^n)$ is the type of the joint sequence $(x^n,y^n)$. $\|\cdot\|_1$ is the L1 norm, i.e., sum of absolute values.

My question is: How the formula (C2) comes out? Although the paper gives a hint regarding degree of freedom of movement and step size $1/n$, but I still could not understand. Thank you for any help!

-
I certainly can't read the excerpt above without knowing more of the definitions. I don't know what $\mathcal X$ is, what $\mathcal X^n$ and so on... –  Anthony Quas Mar 3 '13 at 5:20
$\mathcal{X}$ is the alphabet of symbols for $X$. $\mathcal{X}^n$ is all the sequence of length $n$ drawn from $\mathcal{X}$. –  zzzhhh Mar 3 '13 at 5:48

I realized that once we suppose $\kappa$, $|\mathcal{X}|$ and $|\mathcal{Y}|$ are all $O(1)$, there is a much simpler argument. For each entry of the matrix that is not in the last column, pick a number from $[-\sqrt n,\sqrt n]$ and select the last number of each row such that the marginal becomes $t$. This gives the required $\sqrt n^{(|\mathcal{Y}|-1)\cdot|\mathcal{X}|}$.

For completeness, here is my $Old$ $answer$: I think they use the following fact: The number of ways to put A (identical) balls into B (ordered) bins is ${A+B-1 \choose B-1}$. If A is big compared to B, this is about $A^{B-1}$. More precisely, I think they suppose $|\mathcal{X}|$ and $|\mathcal{Y}|$ are both $O(1)$. Here is a sketch of the computation (not rigorous at all!!!):

In the problem, first we have to decide in which rows the at most $\kappa \sqrt n$ difference will appear, so we put at most $\kappa \sqrt n$ balls to $|\mathcal{X}|$ bins, so far, omitting $\kappa$ and summing for the number of balls from 0 to $\sqrt n$, about $\sqrt n\cdot \sqrt n ^{|\mathcal{X}|-1}= 2^{|\mathcal{X}|\log n /2}$ possibilities. Obviously in most cases this distribution will be quite even, so in each row we further have to divide $\kappa \sqrt n/ |\mathcal{X}|$ balls into $|\mathcal{Y}|-1$ bins and then use the last bin to make the marginal equal to $t$, so we get (ignoring $|\mathcal{X}|$ as it is $O(1)$) about $2^{(|\mathcal{Y}|-2)\log n /2}$ possibilities in each row. In total $2^{|\mathcal{X}|\log n /2} \cdot (2^{(|\mathcal{Y}|-2)\log n /2})^{|\mathcal{X}|}$, just what we wanted.

-
Thank you very much for your answer. But I have three questions as follows: (1) in your old answer, when putting at most $\kappa\sqrt{n}$ balls to $|\mathcal{X}|$ bins and summing for the number of balls from 0 to $\sqrt{n}$ if omitting $\kappa$, I think the total possibilities should be $\sum\limits_{b=0}^{\sqrt{n}}b^{|\mathcal{X}|-1}$. Why you say it is $\sqrt{n}\cdot\sqrt{n}^{|\mathcal{X}|-1}$? (2)Why does "in most cases this distribution will be quite even" so that the number of balls for each row can be obtained by dividing the total balls $\kappa\sqrt{n}$ by $|\mathcal{X}|$? –  zzzhhh Mar 24 '13 at 6:55
The third question is here: (3)For the new answer, since the number of balls in any entry of the matrix, including those in the last column, should not be negative, we can not pick any number freely from $[-\sqrt{n},\sqrt{n}]$. So the number of actual pmfs in $\mathcal{T}_{s^*}$ is less than $\sqrt{n}^{(|\mathcal{Y}|-1)\cdot|\mathcal{X}|}$. Therefore, under this constraint, how to understand the new answer? –  zzzhhh Mar 24 '13 at 6:57
(1) Because that is approximately that much. If you some from $\sqrt n/2$ to $\sqrt n$, you already get about this much. –  domotorp Mar 24 '13 at 7:07
(2) I don't see what is the question here - is it why the distribution is close to even in most cases? You can simply upper bound the cases when in a row the total is, say, 1/10 of the given value and see these do not contribute much. –  domotorp Mar 24 '13 at 7:09
(3) You are right, this is a problem indeed. If $s^*$ is some fix distribution with positive entries while $n\rightarrow\infty$, then the proof is correct, but otherwise not necessarily. E.g., if $s^*$ is zero in all but one row, then we cannot put any coins in the other rows, so we simply get $2^{|\mathcal Y|\log n}$. Either the Lemma is incorrect, or they allow negative entries, or something else is known about $s^*$. –  domotorp Mar 24 '13 at 7:16

Since I can not find the check sign to accept an answer, I hereby declare that I accept domotorp's answer to my question, and sincerely express my appreciation to him for taking time and effort on my question. In addition, I would like to ask the administrator to help me accept domotorp's answer and in turn transfer the 200 bounty to him. Thank you.

-
Apparently, you did not award the bounty in time. The points are now lost and you can no longer accept an answer. –  François G. Dorais Mar 26 '13 at 23:43