Timeline for A question about the size of a L1 ball
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 24, 2013 at 23:01 | comment | added | zzzhhh | Thank you so much for your reply. For question (1), could you please explain in more detail why $\sum\limits_{b=0}^{\sqrt{n}}b^{|\mathcal{X}|-1}$ is approximately equal to $\sqrt{n}\cdot\sqrt{n}^{|\mathcal{X}|-1}$? | |
| Mar 24, 2013 at 7:16 | comment | added | domotorp | (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^*$. | |
| Mar 24, 2013 at 7:09 | comment | added | domotorp | (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. | |
| Mar 24, 2013 at 7:07 | comment | added | domotorp | (1) Because that is approximately that much. If you some from $\sqrt n/2$ to $\sqrt n$, you already get about this much. | |
| Mar 24, 2013 at 6:57 | comment | added | zzzhhh | 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? | |
| Mar 24, 2013 at 6:55 | comment | added | zzzhhh | 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}|$? | |
| Mar 23, 2013 at 16:41 | history | edited | domotorp | CC BY-SA 3.0 |
added 428 characters in body; edited body
|
| Mar 23, 2013 at 15:51 | history | answered | domotorp | CC BY-SA 3.0 |