Skip to main content
MathOverflow

Return to Question

deleted 34 characters in body
Source Link
catbow
catbow
  • 41
  • 6

I am in interested into the following problem. We are given an alphabet $\Sigma$ of $k$ letters and a fixed string $S_1$ of length $l$ defined over $\Sigma$. Given a probability distribution $D$ over $\Sigma$, we sample another string $S_2$ from the set of possible strings defined over $\Sigma$ and with exactly length $n$. Each letter is $S_2$ is sampled independently. We consider that $S_1$ is a substring of $S_2$ if there exists two strings $p$ and $q$ such that: $S_2 = p S_1 q$. What is the probability that $S_1$ is a substring of $S_2$? Additional assumptions could be made about D.

For a uniform distribution, it is a combinatoric problem which solution has been studied for example in: https://stackoverflow.com/questions/6790620/probability-of-3-character-string-appearing-in-a-randomly-generated-password

Would you please have any insight about how it generalizes to any distribution of mean $\mu$ and standard deviation$D$ over $\sigma$$\Sigma$?

I am in interested into the following problem. We are given an alphabet $\Sigma$ of $k$ letters and a fixed string $S_1$ of length $l$ defined over $\Sigma$. Given a probability distribution $D$, we sample another string $S_2$ from the set of possible strings defined over $\Sigma$ and with exactly length $n$. We consider that $S_1$ is a substring of $S_2$ if there exists two strings $p$ and $q$ such that: $S_2 = p S_1 q$. What is the probability that $S_1$ is a substring of $S_2$? Additional assumptions could be made about D.

For a uniform distribution, it is a combinatoric problem which solution has been studied for example in: https://stackoverflow.com/questions/6790620/probability-of-3-character-string-appearing-in-a-randomly-generated-password

Would you please have any insight about how it generalizes to any distribution of mean $\mu$ and standard deviation $\sigma$?

I am in interested into the following problem. We are given an alphabet $\Sigma$ of $k$ letters and a fixed string $S_1$ of length $l$ defined over $\Sigma$. Given a probability distribution $D$ over $\Sigma$, we sample another string $S_2$ with length $n$. Each letter is $S_2$ is sampled independently. We consider that $S_1$ is a substring of $S_2$ if there exists two strings $p$ and $q$ such that: $S_2 = p S_1 q$. What is the probability that $S_1$ is a substring of $S_2$? Additional assumptions could be made about D.

For a uniform distribution, it is a combinatoric problem which solution has been studied for example in: https://stackoverflow.com/questions/6790620/probability-of-3-character-string-appearing-in-a-randomly-generated-password

Would you please have any insight about how it generalizes to any distribution $D$ over $\Sigma$?

added 115 characters in body
Source Link
catbow
catbow
  • 41
  • 6

I am in interested into the following problem. We are given an alphabet $\Sigma$ of $k$ letters and a fixed string $S_1$ of length $l$ defined over $\Sigma$. Given a probability distribution $D$, we sample another string $S_2$ from the set of possible strings defined over $\Sigma$ and with exactly length $n$. We consider that $S_1$ is a substring of $S_2$ if there exists two strings $p$ and $q$ such that: $S_2 = p S_1 q$. What is the probability that $S_1$ is a substring of $S_2$? Additional assumptions could be made about D.

For a uniform distribution, it is a combinatoric problem which solution has been studied for example in: https://stackoverflow.com/questions/6790620/probability-of-3-character-string-appearing-in-a-randomly-generated-password

Would you please have any insight about how it generalizes to any distribution of mean $\mu$ and standard deviation $\sigma$?

I am in interested into the following problem. We are given an alphabet $\Sigma$ of $k$ letters and a fixed string $S_1$ of length $l$ defined over $\Sigma$. Given a probability distribution $D$, we sample another string $S_2$ from the set of possible strings defined over $\Sigma$ and with exactly length $n$. What is the probability that $S_1$ is a substring of $S_2$? Additional assumptions could be made about D.

For a uniform distribution, it is a combinatoric problem which solution has been studied for example in: https://stackoverflow.com/questions/6790620/probability-of-3-character-string-appearing-in-a-randomly-generated-password

Would you please have any insight about how it generalizes to any distribution of mean $\mu$ and standard deviation $\sigma$?

I am in interested into the following problem. We are given an alphabet $\Sigma$ of $k$ letters and a fixed string $S_1$ of length $l$ defined over $\Sigma$. Given a probability distribution $D$, we sample another string $S_2$ from the set of possible strings defined over $\Sigma$ and with exactly length $n$. We consider that $S_1$ is a substring of $S_2$ if there exists two strings $p$ and $q$ such that: $S_2 = p S_1 q$. What is the probability that $S_1$ is a substring of $S_2$? Additional assumptions could be made about D.

For a uniform distribution, it is a combinatoric problem which solution has been studied for example in: https://stackoverflow.com/questions/6790620/probability-of-3-character-string-appearing-in-a-randomly-generated-password

Would you please have any insight about how it generalizes to any distribution of mean $\mu$ and standard deviation $\sigma$?

tex and spelling and irrelevant tag
Source Link
Amir Sagiv
Amir Sagiv
  • 3.6k
  • 1
  • 25
  • 54

I am in interested into the following problem. We are given an alphabet $\Sigma$ of k$k$ letters and a fixed string $S_1$ of length l$l$ defined over $\Sigma$. Given a probability distribution D$D$, we sample another string $S_2$ from the set of possible strings defined over $\Sigma$ and with exactly length n$n$. What is the probability that $S_1$ is a substring of $S_2$? Additional assumptions could be made about D.

For a uniform distribution, it is a combinatoric problem which solution has been studied for example in: https://stackoverflow.com/questions/6790620/probability-of-3-character-string-appearing-in-a-randomly-generated-password

Would you please have any insight about how it generalisesgeneralizes to any distribution of mean $\mu$ and standard deviation $\sigma$?

I am in interested into the following problem. We are given an alphabet $\Sigma$ of k letters and a fixed string $S_1$ of length l defined over $\Sigma$. Given a probability distribution D, we sample another string $S_2$ from the set of possible strings defined over $\Sigma$ and with exactly length n. What is the probability that $S_1$ is a substring of $S_2$? Additional assumptions could be made about D.

For a uniform distribution, it is a combinatoric problem which solution has been studied for example in: https://stackoverflow.com/questions/6790620/probability-of-3-character-string-appearing-in-a-randomly-generated-password

Would you please have any insight about how it generalises to any distribution of mean $\mu$ and standard deviation $\sigma$?

I am in interested into the following problem. We are given an alphabet $\Sigma$ of $k$ letters and a fixed string $S_1$ of length $l$ defined over $\Sigma$. Given a probability distribution $D$, we sample another string $S_2$ from the set of possible strings defined over $\Sigma$ and with exactly length $n$. What is the probability that $S_1$ is a substring of $S_2$? Additional assumptions could be made about D.

For a uniform distribution, it is a combinatoric problem which solution has been studied for example in: https://stackoverflow.com/questions/6790620/probability-of-3-character-string-appearing-in-a-randomly-generated-password

Would you please have any insight about how it generalizes to any distribution of mean $\mu$ and standard deviation $\sigma$?

added 30 characters in body
Source Link
catbow
catbow
  • 41
  • 6
Source Link
catbow
catbow
  • 41
  • 6