Welcome to our community

Be a part of something great, join today!

Probability to realize string using subsequences

MonD

New member
Feb 3, 2014
2
Given a input string and 'n' random subsequences of that string , what is the probability of realizing original string using these subsequences correctly?

Example :

Given string = "MISSISSIPPI"
Subsequences:
1) "MISS"
2) "III"
3) "MIP"
4) "SIS"
5) "IS"
6 ) "SP"
7) "MP"


How many subsequences will be required for optimal probability?
Is there any specific structure for subsequences for optimal probability?
 

MarkFL

Administrator
Staff member
Feb 24, 2012
13,775
Re: probability to realize string using subsequences

Can you post what you have tried or what your thoughts are on how to begin? This will give our helpers a better idea how best to help you. :D
 

MonD

New member
Feb 3, 2014
2
Re: probability to realize string using subsequences

Can you post what you have tried or what your thoughts are on how to begin? This will give our helpers a better idea how best to help you. :D
Input
string of length 'm'
'k' subsequences of the string each of length 'n' (n <m)

What is the probability that by using these subsequences we can come up with the original string?
 

springfan25

New member
Mar 3, 2012
14
i still dont understand the question. post #1 doesn't appear to have substrings of the same length as you required in post #3.

Its also not clear what you mean by probablility of "getting the original string" from your substrings.