8
$\begingroup$

Let $A=(a_{ij})$ be an infinite doubly stochastic matrix. Does there necessarily exist a subsequence $\{n_k\}_{k=1}^\infty$ such that $$ \lim_{k\to\infty}\frac{1}{n_k}\sum_{i=1}^{n_k}\sum_{j=1}^{n_k}a_{ij} >0?$$

In a previous post A question on the partial sum of infinite doubly stochastic matrix, Iosif Pinelis constructed a counterexample for the whole sequence.

$\endgroup$
0

1 Answer 1

11
$\begingroup$

No. Enumerate all positive integers which are not powers of $2$: $3=n_1<n_2<n_3<\dots$ and partition positive integers into two-element sets $\{n_k,2^{k-1}\}$. Let $a_{i,j}=1$ if the set $\{i,j\}$ is such a two-element set, and let $a_{i,j}=0$ otherwise. We get a symmetric bistochastic matrix, and $1$'s are only in the rows or columns indexed by a power of $2$. We have $O(\log n)$ such entries in a square $\{1,2,\dots,n\}^2$.

$\endgroup$
3
  • $\begingroup$ Thank you very much, Fedor and Iosif ! Now it is clear to me. $\endgroup$
    – user118240
    Dec 7, 2017 at 13:38
  • $\begingroup$ @MaxAlekseyev : If you take the pairs, you will get $1$'s only in columns indexed by $2^{k-1}$. $\endgroup$ Dec 7, 2017 at 16:12
  • $\begingroup$ Yes, it seems that one also needs more 1's in the columns (not indexed by $2^{k-1}$) to make it doubly stochastic. $\endgroup$
    – user118240
    Dec 7, 2017 at 16:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.