Let $P\in\mathbb{R}^{n\times n}$ be a doubly-stochastic matrix. That is: $$P(x,y)\geq 0,\quad \sum_xP(x,y)=1,\quad \sum_yP(x,y)=1.$$ I would like to know if lower and upper bounds on the sample complexity of the following problem are known: Given $\epsilon>0$, what is the number of steps required to learn a description $\hat{P}$ of a doubly stochastic matrix satisfying $$\|P-\hat{P}\|_{1\to 1}\leq \epsilon$$ with probability at least $2/3$, where a step $t$ is defined as follows:
- The learner chooses an input probability distribution $p_{0,t}$ and an integer $m_t$.
- The learner then obtains a sample distributed according to $P^{m_t}p_{0,t}$.
I am interested in both the adaptive setting (i.e. $p_t$ and $m_t$ can depend on previous steps) and the non-adaptive case.
One trivial strategy is to pick each canonical basis vector $\mathcal{O}(n\epsilon^{-2})$ times as the initial distribution and estimate the output distribution of each column in TV distance. This gives $\mathcal{O}(n^2\log(n)\epsilon^{-2})$ samples. But is this optimal?
