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.
