<p>What is known about the following problem?</p>

<blockquote>
  <p>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$.</p>
</blockquote>

<p><em>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\}$.</em></p>

CC BY-SA 3.0
2014-10-24T16:17:34.743Z
I think that it is a variant of the problem of reconstructing strings from random traces (in which every trace have the same length $t$); see for example [this paper](http://www.maths.lse.ac.uk/Personal/batu/papers/delch.pdf)
Marzio De Biasi
CC BY-SA 3.0
2014-10-24T17:10:56.283Z
Is it a single random sample, as seems to be written, but makes no sense to me, or a large enough collection of random samples? CC @D.W.
babou
CC BY-SA 3.0
2014-10-25T05:49:15.967Z
Is it intentional that the definition of subsequence allows φ to be non-decreasing instead of increasing?  According to the current definition (Revision 6), “ccc” is a subsequence of “abcde”.
Tsuyoshi Ito
CC BY-SA 3.0
2014-10-27T13:43:20.113Z
You're right @Tsuyoshi Ito, it should be increasing.
user28702
CC BY-SA 3.0
2014-10-27T14:55:12.877Z
Cross-posted to http://mathoverflow.net/questions/185500
Emil Jeřábek
CC BY-SA 3.0
2014-10-30T21:50:58.230Z
It looks like this question was [answered](http://mathoverflow.net/a/185520/8239) on MO, so I am closing this version.
Artem Kaznatcheev
<ds.algorithms>
Reconstructing a string from random samples
user28702
# Reconstructing a string from random samples

(Asked by: username_0 on 2014-10-24)

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\}$.*

**Tags:** ds.algorithms
> **Comments:**
> **username_1**: I think that it is a variant of the problem of reconstructing strings from random traces (in which every trace have the same length $t$); see for example [this paper](http://www.maths.lse.ac.uk/Personal/batu/papers/delch.pdf)  
> **username_2**: Is it a single random sample, as seems to be written, but makes no sense to me, or a large enough collection of random samples? CC @D.W.  
> **username_3**: Is it intentional that the definition of subsequence allows φ to be non-decreasing instead of increasing?  According to the current definition (Revision 6), “ccc” is a subsequence of “abcde”.  
> **username_0**: You're right @Tsuyoshi Ito, it should be increasing.  
> **username_4**: Cross-posted to http://mathoverflow.net/questions/185500  
> **username_5**: It looks like this question was [answered](http://mathoverflow.net/a/185520/8239) on MO, so I am closing this version.  

---

## 0 answers

