What is known about the following problem?



> 
> Reconstruct a string $\sigma$ of known length $n$ over a known
>  alphabet $\Sigma$ from a collection of uniformly and independently
>  chosen $k$-long subsequences of $\sigma$ where $k$ is fixed between
>  $0$ and $n$.
> 
> 
> 


*Recall that a $k$-long subsequence of $\sigma=\langle \sigma\_1,\ldots,\sigma\_n\rangle$ is a sequence $\langle \sigma\_{\varphi(1)},\dots,\sigma\_{\varphi(k)}\rangle$ where $\varphi$ is an increasing function from $\{1,\ldots,k\}$ to $\{1,\ldots,n\}$.*



Reconstructing a string from random samples
Given the string $\sigma$, for any word $x$ of length $k$ the probability $P\_{n,k}(\sigma, x)$ 
that a randomly chosen $k$-long subsequence matches $x$ can be computed, e.g. using
$$ P\_{n,k}(\sigma,x) = \dfrac{k}{n} \delta\_{\sigma\_1, x\_1} P\_{n-1,k-1}(\sigma',x') + \left(1 - \dfrac{k}{n}\right) P\_{n-1,k}(\sigma',x)$$
where $\sigma'$ and $x'$ are $\sigma$ and $x$ respectively with the first symbol removed. If the distributions for different $\sigma$ are different, in principle we can take enough samples to classify $\sigma$ with high probability.
But if two $\sigma$'s have the same distribution, we can't distinguish them.


For example, take $n=4$, $k=2$ and the alphabet $\{0,1\}$, Here are all the 
$P\_{4,2}$:


$$ \left[ \begin {array}{ccccc} &[0,0]&[0,1]&[1,0]&[1,1]
\\ [0,0,0,0]&1&0&0&0\\ [0,0,0,1]&1
/2&1/2&0&0\\ [0,0,1,0]&1/2&1/3&1/6&0
\\ [0,0,1,1]&1/6&2/3&0&1/6\\ [0,1,0
,0]&1/2&1/6&1/3&0\\ [0,1,0,1]&1/6&1/2&1/6&1/6
\\ [0,1,1,0]&1/6&1/3&1/3&1/6\\ [0,
1,1,1]&0&1/2&0&1/2\\ [1,0,0,0]&1/2&0&1/2&0
\\ [1,0,0,1]&1/6&1/3&1/3&1/6\\ [1,0
,1,0]&1/6&1/6&1/2&1/6\\ [1,0,1,1]&0&1/3&1/6&1/2
\\ [1,1,0,0]&1/6&0&2/3&1/6\\ [1,1,0
,1]&0&1/6&1/3&1/2\\ [1,1,1,0]&0&0&1/2&1/2
\\ [1,1,1,1]&0&0&0&1\end {array} \right] 
$$


Note that $\sigma = [0,1,1,0]$ and $\sigma = [ 1,0,0,1]$ both have the same
distribution. So these two cannot be distinguished by their distributions of $2$-long subsequences.


EDIT: For another example, for $n=7$ and $k=3$, $\sigma = [1, 0, 0, 1, 1, 1, 0]$
and $\sigma = [0, 1, 1, 1, 0, 0, 1]$ can't be distinguished by their distributions of $3$-long subsequences. But for $n=6$, all $\sigma \in \{0,1\}^6$ can be distinguished
by their distributions of $3$-long subsequences.


