A question about the size of a L1 ball

Question

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, DOI: 10.1109/TIT.2009.2032803. The image below is an excerption of the paper where I have a question.

In this Appendix, we prove Lemma 5. Fix $x^n\in\mathcal X^n$ and type $s\in \mathcal T_n(\mathcal X\times\mathcal Y)$ according to the lemma's statement. Around $s^*$, we define the following type set: $$\mathcal T_{s^*} \overset{\triangle}= \left\{s\in \mathcal T_n(\mathcal X\times\mathcal Y); \| s-s^* \|_1 \le \frac\kappa{\sqrt{n}}, s_{\mathcal X}=t\right\}.$$ We see that the set $$B(x^n,s^*) = \{y^n\in\mathcal Y^n; \tau(x^n,y^n)\in \mathcal T_{s^*}\}.$$ We pause at this moment to discuss some properties of the set $\mathcal T_{s^*}$. When $n$ is sufficiently large, we see that $\mathcal T_{s^*}$ is a L1 ball centered at $s^*$ and thus symmetric with respect to $s^*$, i.e., $$\sum_{s\in\mathcal T_{s^*}} \frac{s}{|\mathcal T_{s^*}|} = s^*.\tag{C1}$$ Furthermore, observe that there are $|\mathcal X| |\mathcal Y|-|\mathcal X|$ degrees of freedom to move the entries of $s^*$ at step size $1/n$ to obtain a type in $\mathcal T_{s^*}$. This implies that $$|\mathcal T_{s^*}|=2^{\frac{|\mathcal X| |\mathcal Y|-|\mathcal X|}2\log n+O(1)}.\tag{C2}$$

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!

Answer 1

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.

Answer 2

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.