GT 6: Thử nhóm bất ứng biến giải mã nhanh

6. Thử nhóm bất ứng biến giải mã nhanh

6.1. Ý tưởng của Kautz-Singleton

Hồi 1964, Kautz và Singleton đề xuất cách xây dựng ma trận ${d}$ -phân-cách dựa trên hai ý tưởng chính. Thứ nhất là nếu các cột của ma trận có “cân nặng” (số số ${1}$ trên cột) đủ lớn và nếu hai cột bất kỳ có phần giao đủ nhỏ thì ma trận sẽ là ma trận phân cách. Thứ hai là ta có thể dùng phương pháp nối mã (code concatenation) để xây dựng một ma trận thỏa tính chất thứ nhất. Chúng ta thảo luận ý tưởng của Kautz-Singleton trước, sau đó chỉ ra cách dùng ý tưởng này và một ý mới để xây dựng ma trận phân cách giải mã nhanh được.

Bổ đề 1 Gọi ${{\bf M}}$ là một ma trận nhị phân ${t \times N}$ mà mỗi cột có cân nặng ít nhất là ${w}$ , và phần giao của hai cột bất kỳ (các số ${1}$ chung của hai cột) có lực lượng nhiều nhất là ${\lambda}$ . Thì, ${{\bf M}}$ là ma trận ${d}$ -phân-cách với bất kỳ ${d}$ nào thỏa mãn ${d\lambda+1 \leq w}$ . Cụ thể là ${{\bf M}}$ sẽ là ma trận ${\left\lfloor \frac{w-1}{\lambda} \right\rfloor}$ -phân-cách.

Bổ đề này dễ chứng minh. Ta nói tiếp ý tưởng thứ hai. Trước hết hãy định nghĩa phép nối mã.

Gọi ${C_{\text{out}}}$ là một mã ${(n_1,k_1)_q}$ , nghĩa là một ánh xạ từ ${\mathbb F_q^{k_1}}$ vào ${\mathbb F_q^{n_1}}$ , trong đó ${q = 2^{k_2}}$ . (Phép nối mã có thể định nghĩa tổng quát hơn, nhưng ta không cần điều đó.) Như vậy, mỗi ký tự mã của ${C_{\text{out}}}$ là một thành viên của tập ${\mathbb F_q}$ gồm ${2^{k_2}}$ phần tử, và vì thế cũng có thể xem như một thành viên của tập ${\mathbb F_2^{k_2} = \{0,1\}^{k_2}}$ . Mỗi một từ mã của ${C_{\text{out}}}$ có ${n_1}$ vị trí. Mã ${C_{\text{out}}}$ sẽ được gọi là mã ngoài (outer code).

Đến đây, xét ${n_1}$ mã ${(n_2,k_2)_2}$ ký hiệu là ${C^1_{\text{in}}, C^2_{\text{in}}, \cdots, C^{n_1}_{\text{in}}}$ . Tức là, với mọi ${i \in [n_1]}$ thì ${C^i_{\text{in}}}$ là một ánh xạ ${C^i_{\text{in}}: \mathbb F_2^{k_2} \rightarrow \mathbb F_2^{n_2}}$ . Các mã ${C^1_{\text{in}}, \cdots, C^{n_1}_{\text{in}}}$ được gọi là các mã trong.

Mã nối của mã ngoài và các mã trong, ký hiệu là ${C_{\text{out}} \circ (C^1_{\text{in}}, \cdots, C^{n_1}_{\text{in}})}$ , là một mã ${(n_1n_2,k_1k_2)_2}$ được định nghĩa tự nhiên như sau. Cho một thông điệp ${{\bf m} \in \mathbb F_2^{k_1k_2} = (\mathbb F_2^{k_2})^{k_1}}$ , gọi ${(x_1,\dots, x_{n_1}) = C_{\text{out}}({\bf m})}$ . Chú ý rằng ${x_i \in \mathbb F_2^{k_2}}$ . Thì

$\displaystyle C_{\text{out}} \circ (C^1_{\text{in}}, \cdots, C^{n_1}_{\text{in}})({\bf m}) = (C^1_{\text{in}}(x_1), \cdots, C^{n_1}_{\text{in}}(x_{n_1})).$

Nói cách khác, mỗi ký tự của một mã tự ngoài được thay bằng mã tự trong tương ứng. Một mã trong đơn giản nhất là mã đơn vị ${I_q: \mathbb F_2^{k_2} \rightarrow \mathbb F_2^{2^{k_2}}}$ , trong đó mỗi thành viên của ${\mathbb F_2^{k_2}}$ được ánh xạ 1-1 đến một vector đơn vị khác nhau của ${F_2^{2^{k_2}}}$ .

Bây giờ, xét ${C_{\text{out}}}$ là mã RS với các tham số ${[n_1,k_1,n_1-k_1+1]_q}$ , và tất cả các mã trong đều là mã đơn vị ${I_q}$ . Đặt các từ mã của mã nối vào các cột của một ma trận ${{\bf M}}$ . Ma trận này có kích thước ${n_12^{k_2} \times 2^{k_1k_2}}$ . Mỗi cột của ma trận có cân nặng bằng đúng ${n_1}$ . Khoảng cách Hamming giữa hai cột khác nhau ít nhất là ${n_1-k_1+1}$ , do đó phần chung giữa hai cột có kích thước nhiều nhất là ${k_1-1}$ . Vì thế, theo bổ đề 1 thì ${{\bf M}}$ là ma trận ${d}$ -phân-cách với

$\displaystyle d = \left\lfloor \frac{n_1-1}{k_1-1} \right\rfloor > \left\lfloor \frac{n_1}{k_1} \right\rfloor.$

Ngược lại, nếu ta bắt đầu với ${N}$ và ${d}$ thì ta có thể xây dựng một ma trận ${d}$ -phân-cách ${t \times N}$ theo cách trên miễn là ta chọn các tham số sao cho ${N = 2^{k_1k_2}}$ , ${n_1=dk_1}$ . Ta sẽ đạt được tổng số hàng

$\displaystyle t = n_12^{k_2} = dk_12^{k_2}.$

Do mã RS phải thỏa điều kiện ${k_1\leq n_1 \leq q=2^{k_2}}$ , ta phải có ${dk_1 \leq 2^{k_2}}$ nữa. Để có ${t}$ càng nhỏ càng tốt, có thể chọn ${k_2 = \log_2(d\log_2N)}$ nghĩa là ${2^{k_2} = d\log N}$ . Khi đó ${k_1 = \frac{\log_2N}{k_2} = \frac{\log_2N}{\log_2(d\log_2N)}}$ . Rõ ràng là ${dk_1 \leq 2^{k_2}}$ như mong đợi, và tổng số hàng của ma trận này là ${t = O(d^2\log^2N)}$ . Cuối cùng, phép xây dựng này chỉ có lý khi ${k_1\geq 1}$ ; điều này được thỏa mãn khi ${d}$ cỡ ${N/\log N}$ trở xuống. Chặn Bassalygo cho phép ta giả sử vùng giá trị đó của ${d}$ .

6.2. Cải tiến ý tưởng của Kautz-Singleton

Có hai vấn đề với phép xây dựng của Kautz-Singleton. Vấn đề thứ nhất là ta vẫn không biết cách nào để giải mã hiệu quả. Vấn đề thứ hai là số hàng ${O(d^2\log^2N)}$ của ma trận vẫn còn quá lớn so với phép xây dựng ngẫu nhiên ${O(d^2\log N)}$ .

Chúng ta phác thảo một ý tưởng để giải quyết vấn đề thứ nhất. Nếu dùng thuật toán giải mã ngây thơ thì tốn thời gian ${O(Nt)}$ , quá lớn. Nếu ta có cách nào đó chỉ ra nhanh chóng một tập ${m}$ cột, bao gồm cả các cột dương tính, rồi chạy thuật toán ngây thơ thì tốn thời gian chỉ ra ${m}$ cột nọ cộng với khoảng ${O(mt)}$ nữa mà thôi. Có thể nào tận dụng được các tính chất của mã RS không? Hãy xét vector kết quả ${{\bf r} = (r_1, \dots, r_{n_1})}$ , trong đó ${r_i \in \{0,1\}^{q}}$ . Mỗi ${r_i}$ là vector đặc trưng của một tập ${S_i \subset [q]}$ , và do chỉ có nhiều nhất ${d}$ cột dương tính, ta biết ${|S_i| \leq d, \forall i}$ . Hơn thế nữa, xét một cột dương tính ${{\bf c} = (c_1, \dots, c_{n_1})}$ bất kỳ thì hiển nhiên ${c_i \in S_i}$ . (Nhớ rằng ${c_i}$ là một vector đơn vị trong ${\{0,1\}^q}$ , và vì thế có thể được đánh đồng với phần tử tương ứng trong ${[q]}$ .) Đến đây thì định lý Guruswami-Sudan cho biết là tồn tại một thuật toán in ra tất cả các cột thỏa tính chất trên, nghĩa là bao gồm tất cả các cột dương tính, trong thời gian poly ${(q,d) = }$ poly ${(d, \log N)}$ . Và, mã RS đảm bảo rằng có nhiều nhất ${m = O(n_1d/k_1) = O(d^2)}$ cột như vậy. Từ đó, thuật toán ngây thơ chỉ cần thêm ${O(mt) = \text{poly}(d,\log N)}$ nữa thôi.

Kế đến, ta phác thảo một ý tưởng giải quyết vấn đề thứ hai. Lý do mà phép xây dựng của Kautz-Singleton cần ${t}$ lớn là vì ta thay mỗi ký tự trong ${\mathbb F_q}$ bằng một vector nhị phân với chiều dài ${2^{k_2}}$ . Có mã trong nào cần chiều dài ngắn hơn mà vẫn giữ thuật toán chạy đúng hay không? Ta cần tính chất gì từ mã trong? Điều ta cần là, từ một vector kết quả con ${r_i}$ , ta có thể chỉ ra tập ${S_i}$ các ký tự có thể dẫn đến kết quả ${r_i}$ một cách nhanh chóng. Và, kích thước của ${S_i}$ phải nhỏ thôi để ${m}$ nhỏ. Nhớ rằng trong định lý Guruswami-Sudan thì thời gian chạy là poly ${(q,l)}$ và ${m = O(n_1l/k_1)}$ nếu ${|S_i|\leq l}$ với mọi ${i}$ . Như vậy, một ý tưởng rất tự nhiên là tìm một ma trận ${d}$ -phân-cách ${{\bf M}_i}$ với ${n_2}$ hàng và ${q=2^{k_2}}$ cột. Sau đó, thay mỗi ký tự trong ${\mathbb F_q}$ bằng cột tương ứng. Khi đó, từ vector kết quả ${r_i}$ ta có thể chỉ ra một tập ${S_i}$ nhiều nhất ${d}$ cột, dùng cách giải mã ngây thơ chẳng hạn. Ngoài ra, vẫn phải đảm bảo là ma trận ${{\bf M}}$ là ${d}$ -phân-cách để có thể chạy thuật toán ngây thơ một lần nữa trong thời gian ${O(mt)}$ .

Trước hết, thời gian chạy của thuật toán là ${n_1O(qn_2) + O(mt)}$ , vẫn chấp nhận được vì với ${q = 2^{k_2} = d\log N}$ như trước thì thời gian chạy là poly ${(d,\log N) = }$ poly ${(t)}$ . Kế đến, hãy bỏ qua yêu cầu rằng ${{\bf M}}$ là ${d}$ -phân-cách để xem ý tưởng này cho ra ma trận ${{\bf M}}$ có kích thước cỡ nào. Ta biết rằng ${n_2}$ chỉ cần cỡ ${n_2 = O(d^2\log q) = O(d^2k_2)}$ . Do đó, ${t = n_1n_2 = d^3k_1k_2 = d^3\log N}$ . Và cho dù ${{\bf M}_i}$ có số hàng tốt nhất có thể có là ${n_2 = O\left(\frac{d^2}{\log d}\log q\right)}$ thì ${t}$ cũng phải là ${\Omega\left(\frac{d^3}{\log d}\log N\right)}$ . Vì thế, để đạt đến ngưỡng ${t = O(d^2\log N)}$ thì chúng ta phải giảm nhẹ một yêu cầu nào đó.

Cho đến đây, chúng ta vẫn dùng định lý (và thuật toán) Guruswami-Sudan với ${l=d}$ . Nếu ta giảm yêu cầu ${|S_i|\leq d}$ xuống còn ${|S_i| \leq 2d}$ hay thậm chí ${|S_i| \leq 10d}$ thì ${l = \Theta(d)}$ và do đó ${m}$ vẫn đủ nhỏ để đảm bảo giải mã nhanh. Phân tích này cho thấy ta không cần ${{\bf M}_i}$ là một ma trận ${d}$ -phân-cách, mà chỉ cần nó là một ma trận mà, cho vector kết quả ${r_i}$ , ta có thể chỉ ra ${l \geq d}$ cột bao gồm tất cả các cột dương tính là được. Đó là động cơ của định nghĩa ma trận ${(d,l)}$ -phân cách danh sách dưới đây. Chúng ta sẽ chứng minh rằng tồn tại ma trận ${(d,l)}$ -phân-cách danh sách chỉ với ${n_2 = O(d\log q)}$ hàng mà thôi. Từ đó ta sẽ có ${t = O(d^2\log N)}$ như mong đợi.

Cuối cùng, yêu cầu rằng bản thân ${{\bf M}}$ là ${d}$ -phân-cách sẽ được giải quyết bằng một ý tưởng kỹ thuật khác. Chúng ta sẽ chọn các mã trong một cách ngẫu nhiên sao cho mỗi ${{\bf M}_i}$ có tính chất ${(d,l)}$ -phân cách danh sách. Với xác suất gần ${1}$ , ma trận ${{\bf M}}$ sẽ là ${d}$ -phân cách. Để xây dựng ${{\bf M}}$ cụ thể, ta có thể phản ngẫu nhiên hóa phép xây dựng này bằng phương pháp kỳ vọng có điều kiện (conditional expectation method).

Chúng ta đã phác thảo toàn bộ ý tưởng chính của bài báo mới đây của Indyk-Ngo-Rudra ở hội nghị SODA 2010. Phần tới đi vào chi tiết kỹ thuật của các ý tưởng trên.

6.3. Xây dựng ma trận ${d}$ -phân-cách giải mã nhanh

Định nghĩa 2 (Ma trận ${d}$ -phân-cách danh sách) Một ma trận nhị phân ${{\bf M}}$ kích thước ${t \times N}$ được gọi là một ma trận ${(d,l)}$ -phân cách danh sách (list disjunct matrix) nếu nó thỏa tính chất sau đây. Lấy một tập ${S}$ có nhiều nhất là ${d}$ cột của ${{\bf M}}$ , và một tập ${T}$ , không giao với ${S}$ , với ít nhất là ${l}$ cột của ${{\bf M}}$ , thì có ít nhất một hàng ${i}$ mà một cột nào đó trong ${T}$ chứa số ${1}$ còn tất cả các cột khác trong ${S}$ chứa số ${0}$ .

Chú ý rằng ma trận ${d}$ -phân cách là ma trận ${(d,1)}$ -phân-cách danh sách. Giả sử ta dùng ma trận ${d}$ -phân-cách danh sách để thiết kế phép thử nhóm bất ứng biến với nhiều nhất là ${d}$ mẫu dương tính, sau đó dùng phép giải mã ngây thơ để chỉ ra một tập ${P}$ các cột. Dễ thấy rằng ${P}$ chứa tất cả các mẫu dương tính vì phép giải mã ngây thơ không bao giờ loại bỏ một cột dương tính cả. Quan trọng hơn, ta có ${|P| \leq d+l-1}$ vì nếu ${|P| \geq d+l}$ thì ${P}$ chứa tập ${S}$ của nhiều nhất ${d}$ mẫu dương tính và một tập ${T}$ không giao với ${S}$ của ít nhất ${l}$ mẫu âm tính. Khi đó, phải có một cột của ${T}$ bị loại bởi phép giải mã ngây thơ. Do đó, nếu ta dùng các ma trận ${(d,d)}$ -phân cách danh sách làm các mã trong như trong phép xây dựng của Kautz-Singleton thì từ vector kết quả ${{\bf r} = (r_1, \dots, r_{n_1})}$ ta có thể chỉ ra, với mỗi ${i}$ , một tập ${S_i}$ với nhiều nhất ${2d-1<2d}$ các ký tự trong ${\mathbb F_q}$ sao cho, với một mẫu dương tính ${{\bf c} = (c_1, \dots, c_{n_1})}$ bất kỳ thì ${c_i \in S_i, \forall i}$ . Đây là phân tích ta đã giải thích trong phần trước.

Vì thế, nếu ta có thể xây dựng được các ma trận ${(d,d)}$ -phân cách danh sách ${{\bf M}_i}$ dùng làm mã trong với kích thước ${n_2 \times q}$ , và nếu ma trận ngoài ${{\bf M}}$ là một ma trận ${d}$ -phân cách, thì ta có thể giải mã ${{\bf M}}$ trong thời gian

$\displaystyle n_1O(n_22^{k_2}) + O(tn_1l/k_1).$

Ta sẽ chọn các tham số sao cho thời gian này là poly ${(d,t)}$ , và sao cho ${t = O(d^2\log N)}$ .

Trước hết, hãy nói sơ lược về cách xây dựng một ma trận ${(d,d)}$ -phân cách danh sách. Chú ý rằng, trong định nghĩa của ma trận phân cách danh sách, ta có thể giả sử ${2d\leq N}$ , ${|S|=d}$ và ${|T|=d}$ . Ta lại dùng phương pháp xác suất: chọn các ô trong ma trận bằng ${1}$ với xác suất ${p}$ và bằng ${0}$ với xác suất ${1-p}$ . Xác suất mà hai tập ${S}$ và ${T}$ cho trước không thỏa tính chất phân cách danh sách là

$\displaystyle \left[ 1 - (1-(1-p)^d)(1-p)^d \right]^t.$

Do đó, xác suất mà một ma trận ngẫu nhiên ${t \times N}$ không phải là ma trận ${(d,d)}$ -phân cách danh sách nhiều nhất là

$\displaystyle \binom{N}{d}\binom{N-d}{d} \left[ 1 - (1-(1-p)^d)(1-p)^d \right]^t.$

Ta cần chọn ${p}$ sao cho xác suất này nhỏ hơn ${1}$ và ${t}$ càng nhỏ càng tốt. Để xác suất này nhỏ nhất, chọn ${p = 1 - \left(\frac{1}{2}\right)^{1/d}}$ .

$\displaystyle \binom{N}{d}\binom{N-d}{d} \left[ 1 - (1-(1-p)^d)(1-p)^d \right]^t = \left(\frac{Ne}{d}\right)^{2d} (3/4)^t < 1$

nếu ${t = \Omega\left( d\log N \right)}$ . Vì thế, nếu ta dùng các ma trận ${(d,d)}$ -phân-cách danh sách làm các mã trong thì có thể giả sử chúng có kích thước ${n_2 \times q}$ trong đó ${n_2 = O(d\log q) = O(dk_2)}$ .

Tiếc rằng ta cần một điều kiện mạnh hơn khá nhiều: tất cả các mã trong đều là phân cách danh sách cùng một lúc, và ma trận ngoài là ${d}$ -phân cách. Do đó ta phải chọn cách tham số cẩn thận hơn. Và ép xác suất của các sự kiện không mong muốn cùng một lúc.

Định lý 3 Gọi ${d,k_1,k_2}$ là các số nguyên dương bất kỳ sao cho ${10dk_1\leq 2^{k_2}}$ . Định nghĩa ${n_1=10dk_1}$ , ${n_2=480dk_2}$ , ${t=n_1n_2}$ , và ${N=2^{k_1k_2}}$ . (Lưu ý rằng ${n_1\le 2^{k_2}}$ và ${t=O(d^2\log N)}$ .)

Gọi ${C_{\text{out}}}$ là mã RS với các tham số ${\left(n_1,k_1 = \frac{n_1}{10d} \right)_{2^{k_2}}}$ . Thì, tồn tại các mã trong ${C_{\text{in}}^1,\dots,C_{\text{in}}^{n_1}}$ sao cho mỗi mã trong là một mã ${(n_2,k_2)_2}$ và cả hai điều kiện sau đây được thỏa mãn

(a) Đặt ${C^*=C_{\text{out}}\circ(C_{\text{in}}^1,\dots,C_{\text{in}}^{n_1})}$ , thì ${{\bf M}_{C^*}}$ là một ma trận ${t\times N}$ ${d}$ -phân cách.
(b) Với mọi ${i\in [n_1]}$ , ${{\bf M}_i}$ là ma trận ${(d,d)}$ -phân cách danh sách.

Trước khi chứng minh định lý trên, ta chứng minh kết quả chính của loạt bài này, là hệ quả của định lý.

Hệ quả 4 Cho ${N>d\ge 1}$ là các số nguyên bất kỳ. Ta có thể xây dựng được ma trận ${t\times N}$ ${d}$ -phân cách với ${t=O(d^2\log{N})}$ giải mã được trong thời gian ${\text{poly}(d)\cdot t\log^2{t}+O(t^2)}$ .

Chứng minh: Để đơn giản, hãy quên đi việc các tham số là số nguyên. Trước hết, giả sử ${N \geq 100d^2}$ . Đặt ${k_2 = \log_2(10d\log_2 N) \geq 1}$ và ${k_1 = \frac{\log_2 N}{k_2} \geq 1}$ . Khi đó ${10dk_1 \leq 2^{k_2}}$ . Định lý 3 và Bổ đề 1 hoàn tất chứng minh dễ dàng.

Khi ${d<N<100d^2}$ ta có thể bỏ đi ${100d^2 - N}$ cột tùy ý khỏi một ma trận ${t \times 100d^2}$ ${d}$ -phân cách giải mã nhanh được. $\Box$

6.4. Chứng minh Định lý 3

Ta chọn các mã trong một cách ngẫu nhiên, và độc lập với nhau. Gọi các mã trong là ${C_{\text{in}}^i}$ , và ma trận tương ứng là ${{\bf M}_i}$ . Với mỗi ${1\le i\le n_1}$ , chọn ${{\bf M}_i}$ là ma trận nhị phân với kích thước ${n_2\times 2^{k_2}}$ một cách ngẫu nhiên bằng cách gán mỗi ô giá trị ${1}$ với xác suất ${\frac{1}{10d}}$ . Tất cả các ô được chọn độc lập.

Trước hết, ta chặn xác suất mà điều kiện (a) thỏa, nghĩa là ${{\bf M}_{C^*}}$ là ma trận ${d}$ -phân cách. Để cho tiện, viết ${q=2^{k_2}}$ và ${{\bf M}^*={\bf M}_{C^*}}$ .

Theo Bổ đề 1, ${{\bf M}^*}$ là ma trận ${d}$ -phân cách nếu hai sự kiện sau đây cùng đúng:

(i) Mỗi cột có cân nặng ít nhất ${\frac{t}{20d}+1}$ .
(ii) Hai cột bất kỳ có phần giao kích thước nhiều nhất là ${\frac{t}{20d^2}}$

Xét sự kiện (i) trước. Một cột bất kỳ của ${{\bf M}^*}$ đều là một vector ngẫu nhiên trong ${\{0,1\}^t}$ mà mỗi vị trí được gán bằng ${1}$ với xác suất ${\frac{1}{10d}}$ . Do đó, chặn Chernoff cho ta biết xác suất mà một cột của ${\bf M}^*$ có cân nặng ${\leq t/(20d)}$ nhỏ hơn ${e^{-t/(120d)}}$ . Có tất thảy ${N}$ cột, do đó xác suất mà một cột nào đó có cân nặng ${\leq t/(20d)}$ nhỏ hơn ${Ne^{-\frac{t}{120d}}\le N^{-39d}}$ . (Nhớ rằng ${t=4800d^2\log_2{N}}$ .)

Xét sự kiện (ii). Xét hai cột tùy hỉ ${i\neq j\in[N]}$ . Do mã ngoài ${C_{\text{out}}}$ là mã RS với khoảng cách tương đối ít nhất là ${1-\frac{1}{10d}}$ , mã từ thứ ${i}$ và thứ ${j}$ trong ${C_{\text{out}}}$ phải bất đồng ở một tập các vị trí ${S\subseteq[n_1]}$ nào đó thỏa ${|S|=(1-\frac{1}{10d})n_1}$ . Gọi ${A_1\in \{0,1\}^{t(1-\frac{1}{10d})}}$ và ${A_2\in\{0,1\}^{\frac{t}{10d}}}$ là hạn chế của cột thứ ${i}$ của ${{\bf M}^*}$ trên các vị trí trong ${S}$ và ${[N]-S}$ , theo thứ tự. Tương tự, gọi ${B_1}$ và ${B_2}$ là các hạn chế tương ứng của cột ${j}$ . Chúng ta cần chặn biến ngẫu nhiên ${|A_1\cap B_1|+|A_2\cap B_2|}$ .

Hãy bắt đầu với ${|A_1\cap B_1|}$ . Theo định nghĩa của ${A_1}$ và ${B_1}$ , ${A_1\cap B_1 \in\{0,1\}^{t(1-\frac{1}{10d})}}$ chẳng qua là một vector mà mỗi tọa độ được gán bằng ${1}$ độc lập nhau với xác suất ${\frac{1}{100d^2}}$ . Vì thế, chặn Chernoff suy ra

$\displaystyle \begin{array}{rcl} \text{Prob}\left[|A_1 \cap B_1| \geq 2\frac{t}{100d^2}\right] &\leq& \text{Prob}\left[|A_1 \cap B_1| \geq \frac{2}{100d^2}t(1-\frac{1}{10d})\right]\\ & \leq& e^{-\frac{1}{300d^2}t(1-\frac{1}{10d})} \\ & \leq& e^{-t/(600d^2)}. \end{array}$

Kế đến, ta chặn ${|A_2\cap B_2|}$ . Chú ý rằng ${|A_2\cap B_2|\le |A_2|}$ và ${A_2}$ là một vector ngẫu nhiên trong ${\{0,1\}^{\frac{t}{10d}}}$ mà mỗi tọa độ được chọn độc lập bằng ${1}$ với xác suất ${\frac{1}{10d}}$ . Một lần nữa, Chernoff cho ta biết xác suất mà ${|A_2|\ge \frac{2t}{100d^2}}$ nhiều nhất là ${e^{-t/(300d^2)}\leq e^{-t/(600d^2)}}$ .

Từ đó, xác suất mà ${|A_1\cap B_1|+|A_2\cap B_2| < \frac{4t}{100d^2}<\frac{t}{20d^2}}$ ít nhất là ${1 - 2e^{-t/(600d^2)}=1-2e^{-8k_1k_2}\geq 1-2N^{-11}}$ . Do có tất thảy ${\binom{N}{2}}$ chọn lựa cho ${i}$ và ${j}$ , ta kết luận rằng điều kiện (ii) không thỏa với xác suất nhỏ hơn ${N^{-9}}$ . Tổng kết lại thì điều kiện (a) không thỏa với xác suất nhỏ hơn ${1/N^{39d} + 1/N^9\leq 2/N^9}$ .

Bây giờ, ta chặn xác suất mà điều kiện (b) thỏa. Chúng ta sẽ chứng minh rằng, với mọi ${i \in [n_1]}$ , ${{\bf M}_i}$ không là ma trận ${(d,d)}$ -phân cách danh sách với xác suất nhỏ hơn ${q^{-58d}}$ . Từ đó, dùng ${n_1\le 2^{k_2}=q}$ , ta kết luận rằng điều kiện (b) không thỏa với xác suất nhỏ hơn ${q^{-57d}}$ . Như vậy, với xác suất ít nhất ${1-\frac{2}{N^9}-\frac{1}{2^{57dk_2}}>0}$ cả hai tính chất (a) và (b) đều thỏa. Và vì thế, định lý được chứng minh xong.

Phần còn lại là chặn xác suất mà ${{\bf M}_i}$ không là ma trận ${(d,d)}$ -phân cách danh sách. Ta dùng phương pháp như đã dùng trong mục 6.3.; xác suất mà một ${{\bf M}_i}$ nào đó không là ma trận ${(d,d)}$ -phân cách danh sách sẽ nhỏ hơn

$\displaystyle \begin{array}{rcl} && \binom{q}{d}\binom{q-d}{d}\left(1-\left(1-\left(1-\frac{1}{10d}\right)^d\right)\left(1-\frac{1}{10d}\right)^d\right)^{n_2}\\ &\le& q^{2d}\left(1-(1-1/\sqrt[10]{e})\cdot\frac{1}{\sqrt[10]{e}}\right)^{n_2}\\ &\le& q^{2d}2^{-n_2/8}\le q^{-58d}, \end{array}$

trong đó bất đẳng thức cuối cùng đúng là do ${n_2=480dk_2}$ .

Một điểm cuối cùng cần lưu ý là ta có thể phản ngẫu nhiên hóa bằng phương pháp kỳ vọng có điều kiện để xây dựng cụ thể ma trận ${{\bf M}^*}$ luôn mà không cần chọn nó một cách ngẫu nhiên. Kết quả này đơn giản nhưng lắt nhắt về mặt chi tiết.

2 Comments

XuanLong Nguyen

Posted 29/01/2010 at 6:53 am | Permalink

Có typo: Do đó, \href{http://www.cse.buffalo.edu/ {\leq t/(20d)} nhỏ hơn {e^{-t/(120d)}}…..

Bác Hưng dùng chữ “thỏa” thay vì “thỏa mãn” ạ?

Ngô Quang Hưng

Posted 29/01/2010 at 7:52 am | Permalink

Cảm ơn bác Long, tôi đã sửa lại. “Thỏa” theo nghĩa “thỏa điều kiện”, hy vọng là không tù mù quá. Do tôi lười.

GT 6: Thử nhóm bất ứng biến giải mã nhanh

2 Comments

Post a Comment Cancel reply

Thông điệp ngắn

Phản hồi mới

Bài mới

Thư khố

Chuyên Mục

Báo chí

Bảo mật

Blog Việt

Chưa phân loại

Giáo dục

Kỹ thuật

Khoa học khác

Kinh tế, luật pháp, xã hội

Lý thuyết & thuật toán

Mạng

Não học

Toán học

Vật Lý