Düzenleme mesafesi en fazla 3 olan ortalama dize sayısı (daha büyük alfabe)

Dec 21 2020

Bir uzunluk dizisi düşünün $n \geq 3$ bir alfabe üzerinde $\{1,\dots, \sigma\}$. Bir düzenleme işlemi, tek bir sembol ekleme, silme veya değiştirmedir. İki dize arasındaki düzenleme mesafesi, bir dizeyi diğerine dönüştürmek için gereken minimum düzenleme işlemi sayısıdır. Bir dizge verildiğinde$S$ uzunluk $n$ ile $S_i \in \{1,\dots, \sigma\}$, sorum en fazla düzenleme mesafesi olan farklı dizelerin sayısıyla ilgili $3$ itibaren $S$.

Yazalım $g_{k, \sigma}(S)$ alfabe üzerindeki farklı dizelerin sayısı için $\{1,\dots, \sigma\}$ en fazla düzenleme mesafesi olan $k$ itibaren $S$yani $g_{k,\sigma}(S) = |\{S' : d(S', S) \leq k\}|$ nerede $d(-,-)$ düzenleme mesafesidir.

İzin Vermek $X_n$ alfabe üzerinde rastgele bir dizeyi temsil eden rastgele bir değişken olabilir $\{1,\dots, \sigma\}$ uzunluk $n$üniform ve bağımsız olarak seçilen sembollerle.

Bu doğrudan soruma götürüyor:

İzin Vermek $X_n$ rastgele bir uzunluk dizisini temsil eden rastgele bir değişken olmak $n$üniform ve bağımsız olarak seçilen sembollerle. Nedir:

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

İçin $\sigma=2$biz edebilirsiniz açık formülü olsun $(40+6n-4n^2)/2^n-83/2+(331/12)n-6n^2+(2/3)n^3$. Öyleyse sorum şu, alfabe boyutuna bağımlılık nedir?$\sigma$ gibi görünmek?

Yanıtlar

1 BillVanderLugt Dec 30 2020 at 03:15

Değişen ve Değiştirilmemiş Dize Uzunluğu

Yorumuma yanıt olarak başlangıçta belirttiğiniz gibi, dönüştürülen dizenin uzunluğu orijinal dizinin uzunluğundan farklı olabilirse, bu sorun çok daha zor hale gelir çünkü farklı düzenleme işlemleri kümesi (potansiyel olarak farklı bir sonuç verebilecek işlemler) ) aşağıdakilerin 18'ini içerir:

  • uzunluk +3 = 3 ekleme
  • uzunluk +2 = 2 ekleme ve 0 veya 1 ikame
  • uzunluk +1 = 1 ekleme ve 0, 1 veya 2 ikame
  • uzunluk değişmemiş = 0, 1, 2 veya 3 ikame; 1 silme, 1 ekleme ve 0 veya 1 ikame
  • uzunluk -1 = 1 silme ve 0, 1 veya 2 ikame
  • uzunluk -2 = 2 silme ve 0 veya 1 ikame
  • uzunluk -3 = 3 silme

Üstelik, birden çok ekleme veya birden çok silme işlemi gerçekleştirildiğinde, sayma aşırı derecede zorlaşır. Öte yandan, uzunluğun değişmeden kalmasını istiyorsak, dikkate almamız gereken sadece 6 düzenleme kombinasyonumuz var ve sorun daha anlaşılır hale geliyor çünkü bu 6 kombinasyonun hiçbiri birden fazla ekleme veya birden fazla silme içermiyor. Aslında, altı vakanın her biri için sayma nispeten basit hale gelir; en zor bit, iki farklı düzenleme işleminin aynı dizeyi üreteceği durumlarda örneklerin iki kez sayılmasını önlemek için indirim yapmaktır - başka bir sorunun yanıtında çözülen bir sorun .

Altı Durum ve Aşırı Sayım Tehlikesi Öncelikle
rulmanlarımızı almak için bu mantığı genelleştirebiliriz :

  • Dize korunmalıdır $n$ semboller.
  • Aynı sembollerden oluşan beklenen grup sayısı: $\frac{n+1}{\sigma}$
  • Bitişik, özdeş sembol çiftlerinin beklenen sayısı: $\frac{n-1}{\sigma}$
  • Uç sayısı 2'dir.

Beş olası tek düzenleme türünün ayrıntılı bir şekilde ele alınması, böylece şunları sağlar:

  • Olası oyuncu değişikliği sayısı $n(\sigma-1)$
  • Bir grup özdeş sembolün beklenen küçülme sayısı: $\frac{n+1}{\sigma}$
  • Aynı sembole sahip bir grup özdeş sembolden beklenen genişletme sayısı: $\frac{n+1}{\sigma}$
  • Aynı sembole sahip özdeş semboller grubuna beklenen ekleme sayısı şöyledir: $\frac{n-1}{\sigma}$
  • Başında veya sonunda farklı bir karakterin olası ekleme sayısı: $2(\sigma-1)$

Şimdi bu temel mantığı altı durumumuzun her birine uygulayabiliriz:

  1. düzenleme
    yok Herhangi bir düzenleme yapılmazsa yalnızca orijinal dizge elde edilir, bu nedenle bu durum için 1 sonuç alınır.

  2. bir ikame
    var$n$ farklı semboller ve $\sigma-1$ her birinin farklı bir sembolle ikame edilebileceği yollar, bu nedenle $n(\sigma-1)$ Sonuçlar.

  3. iki ikame
    vardır$\binom{n}{2}$ farklı çiftler ve $(\sigma-1)^2$ her birini değiştirmenin yolları: $\binom{n}{2}(\sigma-1)^2$ Sonuçlar.

  4. üç oyuncu değişikliği
    vardır$\binom{n}{3}$ farklı üçlüler ve $(\sigma-1)^3$ her birini değiştirmenin yolları: $\binom{n}{3}(\sigma-1)^3$.

  5. bir silme, bir ekleme, ikame yok
    Bu durum için, bu çözümü aşağıdakiler için genelleyebiliriz :$\sigma=2$ herhangi birine $\sigma$, iki ikamenin bir silme ve bir ekleme ile aynı sonucu vereceği durumları iki kez saymaktan kaçınmak için aynı mantığı kullanmak.

Eklemenin silme işleminin solunda olduğu durumları sayalım ve sonra 2 ile çarpalım. Ekleme ve silme işleminin birleşik etkisi, ilkini değiştirip sonuncuyu kaldırırken aralarındaki tüm bitleri sağa kaydırmaktır. . Bu sonuca en fazla 𝑘 ikameyle de ulaşılabilir, bu yüzden 𝑘> 2'ye ihtiyacımız var. Bir dizi 𝑥s içine 𝑥 eklemek, çalışmanın sonuna 𝑥 eklemekle aynı etkiye sahiptir. Böylece, her zaman eklemenin sağına tamamlayıcı biti ekleyerek farklı efektlere sahip tüm eklemeleri bir kez sayabiliriz. Benzer şekilde, bir çalışma içindeki bir silme işlemi, çalışmanın başlangıcındaki bir silme ile aynı etkiye sahiptir, bu nedenle yalnızca 0 ile 1 arasındaki bir değişikliği takip eden silme işlemlerini saymalıyız. Bu, bize bir başlangıç ​​sayımı verir:

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

Çift sayımı engelleyen karmaşık mantık doğrudan devam ettiğinden, gereken tek değişiklik bir değişkeni değiştirmektir. $\sigma$ sabit için $\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}\;$

Halihazırda iki oyuncu değişikliği olarak kaydedilmiş olan fazla sonuç sayısı aşağıdaki gibi hesaplanabilir: $\sigma=2$:

𝑘 kaydırılmış bitlerde silme işleminden öncekinden başka değişiklik yoksa, o zaman sadece ekleme ve silme işleminin yanındaki bitler değişir ve bunu 2 ikame ile elde edebiliriz, bu nedenle çıkarmak zorundayız

$\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)}\;$

Yine, bizim tek değişikliğimiz ikame etmektir $\sigma$ 2 için:

$\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)}\;$

Ayrıca, kaydırılan bitlerin tümü alternatif sıfırlardan ve birlerden oluşuyorsa, ekleme ve silme işleminin değiştirilmesi aynı etkiyi verir, bu nedenle bu durumda iki kez sayıyorduk ve çıkarmamız gerekiyor

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

Takas $\sigma$ son bir zaman verir:

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

Bu iki fazla sayma (ne yazık ki, sembollerin ikili olduğu zamanki kadar temiz bir şekilde birleştirilemez), daha sonra bu durum tarafından üretilen genel sonuçları vermek için silme / ekleme işlemlerinin ilk sayısından çıkarılır, ancak yukarıdaki 3. durumla değil:

$\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. bir silme, bir ekleme, bir ikame
    Aynı hesaplama son duruma da taşınır. Bununla birlikte, burada, bir silme ve bir eklemenin her bir kombinasyonuna - benzer şekilde, yukarıdaki 4. durumda zaten kaydedilmiş olan üçlü oyuncu değişikliğinin iki kez sayılmasını önlemek için indirilmiştir - üçüncü bir düzenleme eşlik eder: aşağıdakilerden birini içeren bir değişiklik$n-1$silme işleminden sonra kalan orijinal semboller. Bunların her biri$(n-1)$ semboller kabul eder $(\sigma-1)$ yeni ikameler, altıncı ve son durum için toplam sayı:

$\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);$

Bu altı durumun her biri tarafından üretilen (daha önce sayılmamış) sonuçların toplanması, dizinin uzunluğu değişmeden kaldığında beklenen sayıyı vermelidir. Çirkin (belki gereksiz bir şekilde), ama umarım doğrudur.