이 문자열의 조각을 사용하여 문자열에서 주어진 문자의 확률을 계산하는 방법은 무엇입니까?

Question

01001010101001101011과 같은 문자열이 주어지면 여러 부분 문자열을 무작위로 슬라이스 할 수 있습니다. 슬라이싱하는 동안 예기치 않은 노이즈로 인해 일부 문자가 뒤집어 질 수 있다고 가정하십시오 (0->1 또는 1->0). 예를 들어 위치 (1)로부터

Position:......... 
String: 01001010101001101011 

slice1: 1001110101000 
slice2:  1010111001111 
slice3:  10101 
slice4:    1101011 

slice1 시작 위치 4에서 slice2 개시 4에서 slice3 시작하고 slice1 13.에서 slice4 시작, 0 플립 (문자열의 인덱스 0에서 시작한다고 가정) 그것이 1 인 다음 슬라이싱에 0로 내리고 확률이 0.1 인 경우에서의 5 위치 1 및 1에 원래 문자열 하나 개의 특정 위치를 들면 위치 13

에서 0에게 튀긴다; 그 반대의 경우도 마찬가지입니다 (즉, Prob(0->1)=0.1).

문제는 다음과 같습니다. 여러 슬라이스 (각 슬라이스의 길이가 다를 수 있음)와 문자열의 시작 위치 만있는 경우 원래 문자열이 임의의 위치 인 경우 원본 문자열을 알 수 없습니다 , 위치가 1 일 확률을 어떻게 계산할 수 있습니까? ,

p01=0.1; // Probability a ‘0’ in string but flipped to a ‘1’ in a slice 
p10=0.1; // Probability a ‘1’ in string but flipped to a ‘0’ in a slice 
p1=0.5; // Prior probability that any given position in string is a ‘1’ 

우리는 또한 문자열이 0과 1의 임의의 문자열이라고 가정 할 수 있고, 슬라이스시 :

대부분의 위치가 조각에 적어도 한 번 적용됩니다 가정, 우리는 다음과 같은 매개 변수가 각 위치는 독립적으로 샘플링됩니다. 위의 예에서 문자열과 네 개의 슬라이스

, 우리는 이미 각 위치에 대한 다음과 같은 확률이 : 내가 답변 위의 방법을 알아 내려고 시간을 보냈다

Pos Prob 
0 0.500 
1 0.900 
2 0.100 
3 0.100 
4 0.999 
5 0.100 
6 0.999 
7 0.001 
8 0.999 
9 0.500 
10 0.988 
11 0.012 
12 0.012 
13 0.900 
14 0.988 
15 0.500 
16 0.988 
17 0.100 
18 0.900 
19 0.900 

을, 나는 0의 수를 셀 수 s 및 1을 프로그램이있는 각 위치의 모든 조각에 표시합니다. 그러나, 여전히, 특히 위치 4 (1,1,1), 5 (1,0,0), 9 (0,1), 13 (0,1,1)에 대해, 확률을 계산하기 화학식 또는 모델 또는 알고리즘를 찾을 수 없다.

Answer 1

문자열의 각 위치에 대해 n 비트의 양 (조각의 정보)이 있습니다. k이 '1'이라고 가정 해 보겠습니다.

예를 들어, 위치 5에서 우리는 n = 3이고 k = 1입니다.

원래 문자열에 해당 위치에 '1'이 포함되어 있음을 확인하려면 binomial distribution을 사용합니다. 우리는 먼저 n = 3 (그래서 1과 2의 0)이라면 원래의 문자열에서 '0'이 k = 1이 될 확률을 찾아야합니다. 이 경우 : 0.243. 그러면 n = 3이면 '1'이 k = 1이 될 확률이 필요합니다. 이것은 0.027입니다. 이제 우리는 마침내 원래의 문자열에서 '1'이라는 확률을 얻었습니다 : p = 0.027/(0.243 + 0.027) = 0.1

저는 각 위치별로 n과 k를 얻을 수 있다고 가정합니다. C# 또는 Java 코드 :

private float p1 = 0.5; 
private float p01 = 0.1; 
private float p10 = 0.1; 

private float probItsOne(int n, int k) 
{ 
    if (n == 0) 
     return p1; 
    float probByZero = binomial(n, p01, k); // probability a '0' would generate this k, given n 
    float probByOne = binomial(n, p10, n - k); 
    return probByOne/(probByZero + probByOne); 
} 

// (this p is not the same as in my explanation) 
private float binomial(int n, float p, int k) 
{ 
    return combinations(n, k) * Math.Pow(p, k) * Math.Pow(1 - p, n - k); 
} 

private int combinations(int n, int k) 
{ 
    return (int)(factorial(n)/(factorial(k) * factorial(n - k)); 
} 

private long factorial(int n) 
{ 
    long result = 1; 
    for (int i = 2; i <= n; n++) 
     result *= i; 
    return result; 
}