Średnia liczba ciągów z odległością edycji maksymalnie 3 (większy alfabet)

Dec 21 2020

Rozważmy ciąg długości $n \geq 3$ nad alfabetem $\{1,\dots, \sigma\}$. Operacja edycji to wstawienie, usunięcie lub zastąpienie pojedynczego symbolu. Odległość edycji między dwoma ciągami to minimalna liczba operacji edycji potrzebnych do przekształcenia jednego ciągu w drugi. Biorąc pod uwagę ciąg$S$ długości $n$ z $S_i \in \{1,\dots, \sigma\}$, moje pytanie dotyczy liczby różnych ciągów, które mają najwyżej odległość edycji $3$ od $S$.

Napiszmy $g_{k, \sigma}(S)$ dla liczby różnych ciągów nad alfabetem $\{1,\dots, \sigma\}$ które są maksymalnie edycją odległości $k$ od $S$, tj $g_{k,\sigma}(S) = |\{S' : d(S', S) \leq k\}|$ gdzie $d(-,-)$ to odległość edycji.

Pozwolić $X_n$ być zmienną losową reprezentującą losowy ciąg znaków nad alfabetem $\{1,\dots, \sigma\}$ długości $n$, z jednolicie i niezależnie wybranymi symbolami.

To prowadzi bezpośrednio do mojego pytania:

Pozwolić $X_n$ być zmienną losową reprezentującą losowy ciąg o długości $n$, z jednolicie i niezależnie wybranymi symbolami. Co jest:

$$\mathbb{E}(g_{3, \sigma}(X_n))\;?$$

Dla $\sigma=2$możemy otrzymać wyraźną formułę $(40+6n-4n^2)/2^n-83/2+(331/12)n-6n^2+(2/3)n^3$. Więc moje pytanie brzmi, jaka jest zależność od wielkości alfabetu$\sigma$ wygląda jak?

Odpowiedzi

1 BillVanderLugt Dec 30 2020 at 03:15

Zmienna v. Niezmieniona długość struny

Jeśli, jak początkowo wskazałeś w odpowiedzi na mój komentarz, długość przekształconego ciągu może różnić się od długości oryginału, to problem staje się znacznie trudniejszy, ponieważ zestaw odrębnych operacji edycyjnych (operacji, które mogą potencjalnie dać inny wynik ) obejmuje wszystkie 18 z następujących elementów:

  • długość +3 = 3 wstawki
  • długość +2 = 2 wstawienia i 0 lub 1 podstawienia
  • długość +1 = 1 wstawienie i 0, 1 lub 2 podstawienia
  • niezmieniona długość = 0, 1, 2 lub 3 podstawienia; 1 delecja, 1 insercja i 0 lub 1 substytucja
  • długość -1 = 1 delecja i 0, 1 lub 2 podstawienia
  • długość -2 = 2 delecje i 0 lub 1 podstawienia
  • długość -3 = 3 usunięcia

Ponadto zawsze, gdy wykonuje się wielokrotne wstawienia lub wielokrotne usuwanie, liczenie staje się niezwykle trudne. Jeśli z drugiej strony wymagamy, aby długość pozostała niezmieniona, mamy tylko 6 kombinacji edycji do rozważenia i problem staje się łatwiejszy do rozwiązania, ponieważ żadna z tych 6 kombinacji nie obejmuje wielu wstawień lub wielokrotnych usunięć. Rzeczywiście, liczenie dla każdego z sześciu przypadków staje się stosunkowo proste; najtrudniejszą rzeczą jest dyskontowanie, aby uniknąć podwójnego liczenia przypadków, gdy dwie różne operacje edycji dadzą ten sam ciąg - problem rozwiązany w odpowiedzi na inne pytanie .

Sześć przypadków i niebezpieczeństwo nadmiernego przeliczania
Na początku możemy uogólnić tę logikę :

  • Ciąg musi się utrzymywać $n$ symbolika.
  • Oczekiwana liczba grup identycznych symboli to $\frac{n+1}{\sigma}$
  • Oczekiwana liczba sąsiednich, identycznych par symboli to $\frac{n-1}{\sigma}$
  • Liczba końców wynosi 2.

Dokładne rozważenie pięciu możliwych typów pojedynczych edycji daje zatem:

  • Liczba możliwych podstawień wynosi $n(\sigma-1)$
  • Oczekiwana liczba kurczeń grupy identycznych symboli wynosi $\frac{n+1}{\sigma}$
  • Oczekiwana liczba rozwinięć grupy identycznych symboli z tym samym symbolem wynosi $\frac{n+1}{\sigma}$
  • Oczekiwana liczba wstawień do grupy identycznych symboli z tym samym symbolem wynosi $\frac{n-1}{\sigma}$
  • Liczba możliwych wstawień innego znaku na początku lub na końcu wynosi $2(\sigma-1)$

Możemy teraz zastosować tę podstawową logikę do każdego z naszych sześciu przypadków:

  1. bez edycji
    Brak jakichkolwiek zmian daje tylko oryginalny ciąg, więc 1 wynik dla tego przypadku.

  2. jedna zmiana
    Jest$n$ różne symbole i $\sigma-1$ sposób, w jaki każdy może zostać zastąpiony innym symbolem, więc $n(\sigma-1)$ wyniki.

  3. dwa podstawienia
    Istnieją$\binom{n}{2}$ różne pary i $(\sigma-1)^2$ sposoby modyfikacji każdego: $\binom{n}{2}(\sigma-1)^2$ wyniki.

  4. trzy podstawienia
    Istnieją$\binom{n}{3}$ różne tria i $(\sigma-1)^3$ sposoby modyfikacji każdego: $\binom{n}{3}(\sigma-1)^3$.

  5. jedna delecja, jedna wstawka, brak podstawień
    W tym przypadku możemy uogólnić to rozwiązanie dla$\sigma=2$ do każdego $\sigma$, używając tej samej logiki, aby uniknąć podwójnego liczenia tych przypadków, w których dwa podstawienia dałyby ten sam wynik, co jedno usunięcie i jedno wstawienie.

Policzmy przypadki, w których wstawienie znajduje się na lewo od usunięcia, a następnie pomnóżmy przez 2. Połączony efekt wstawienia i usunięcia polega na przesunięciu wszystkich 𝑘 bitów między nimi w prawo podczas zamiany pierwszego i usunięcia ostatniego . Ten wynik można również osiągnąć przez co najwyżej 𝑘 podstawień, więc potrzebujemy 𝑘> 2. Wstawienie 𝑥 w ciągu 𝑥s ma taki sam skutek, jak wstawienie 𝑥 na końcu rozdziału. W ten sposób możemy policzyć wszystkie wstawienia z różnymi efektami raz, zawsze wstawiając bit uzupełniający do tego na prawo od wstawienia. Podobnie, usunięcie w ramach cyklu ma taki sam efekt jak usunięcie na początku cyklu, więc powinniśmy liczyć tylko usunięcia, które następują po zmianie między 0 a 1. To daje nam początkową liczbę:

$2\cdot\frac12\sum_{k=3}^n(n+1-k)=\sum_{k=1}^{n-2}k=\frac{(n-1)(n-2)}2\;$

Ponieważ podstępna logika zapobiegająca podwójnemu liczeniu przenosi się bezpośrednio, jedyną wymaganą modyfikacją jest podstawienie zmiennej $\sigma$ dla ustalonych $\sigma=2$:

$2\cdot\frac{1}{\sigma}\sum_{k=3}^n(n+1-k)=2\cdot\frac{1}{\sigma}\sum_{k=1}^{n-2}k=\frac{(n-1)(n-2)}{\sigma}\;$

Nadliczenie wyników, które zostały już zliczone jako dwa podstawienia, można obliczyć w następujący sposób, gdy $\sigma=2$:

Jeśli nie ma dalszych zmian w przesuniętych bitach 𝑘 innych niż ten poprzedzający usunięcie, to zmieniają się tylko bity obok wstawiania i usuwania i możemy to osiągnąć przy 2 podstawieniach, więc musimy odjąć

$\sum_{k=3}^n\left(\frac12\right)^{k-2}(n+1-k)=\sum_{k=1}^{n-2}\left(\frac12\right)^{n-k-1}k=n-3+2^{-(n-2)}\;$

Ponownie, jedyną naszą modyfikacją jest zastąpienie $\sigma$ dla 2:

$\sum_{k=3}^n\left(\frac1{\sigma}\right)^{k-2}(n+1-k)=\sum_{k=1}^{n-2}\left(\frac1{\sigma}\right)^{n-k-1}k=n-3+{\sigma}^{-(n-2)}\;$

Ponadto, jeśli cały zakres przesuniętych bitów składa się z naprzemiennych zer i jedynek, to zamiana wstawienia i usunięcia daje ten sam efekt, więc w tym przypadku liczyliśmy podwójnie i musimy odjąć

$\sum_{k=3}^n\left(\frac12\right)^{k-1}(n+1-k)\;$

Zamiana $\sigma$ czas końcowy daje:

$\sum_{k=3}^n\left(\frac1{\sigma}\right)^{k-1}(n+1-k)\;$

Te dwa przekroczenia (których, niestety, nie można połączyć tak czysto, jak wtedy, gdy symbole są binarne) są następnie odejmowane od początkowej liczby operacji usuwania / wstawiania, aby uzyskać ogólne wyniki uzyskane w tym przypadku, ale nie w przypadku 3 powyżej:

$\frac{(n-1)(n-2)}{\sigma}\ - \left(n-3+{\sigma}^{-(n-2)}\right) - \sum_{k=3}^n\left(\frac1{\sigma}\right)^{k-1}(n+1-k)\;$

  1. jedno usunięcie, jedno wstawienie, jedno zastąpienie
    To samo obliczenie przenosi się na ostatni przypadek. Tutaj jednak każdej kombinacji jednej delecji i jednej wstawienia - podobnie pomniejszonej o podwójne liczenie potrójnych podstawień już zsumowanych w przypadku 4 powyżej - towarzyszy trzecia zmiana: podstawienie obejmujące jedną z$n-1$oryginalne symbole pozostałe po usunięciu. Ponieważ każdy z nich$(n-1)$ symbole przyznaje $(\sigma-1)$ nowe podstawienia, całkowita liczba szóstego i ostatniego przypadku to:

$\left(\frac{(n-1)(n-2)}{\sigma}\ - \left(n-3+{\sigma}^{-(n-2)}\right) - \sum_{k=3}^n\left(\frac1{\sigma}\right)^{k-1}(n+1-k)\right)(n-1)(\sigma-1);$

Zsumowanie (wcześniej niepoliczonych) wyników uzyskanych przez każdy z tych sześciu przypadków powinno dać oczekiwaną liczbę, gdy długość łańcucha pozostaje niezmieniona. Jest brzydki (być może niepotrzebnie), ale mam nadzieję, że się zgadza.