Có một bài viết khá hay của GS Ngô Quang Hưng, tôi muốn đuợc giới thiệu với các bạn.


PCP 10 — Biến đổi Fourier, định lý Arrow và tính duy lý của sự độc tài

[Only registered and activated users can see links. ]
Như vậy chúng ta đã có chuyến “de-tour” sang các phép xây dựng đồ thị expanders, tính chất của chúng, và tích zig-zag. Đáng lẽ bài kế tiếp này tôi định viết về kết quả [Only registered and activated users can see links. ] của Omer Reingold hồi 2005. Nhưng lại thôi vì thật ra nếu hiểu tích zig-zag rồi thì hiểu [Only registered and activated users can see links. ] của Reingold không khó khăn gì. Năm đó có chú Vladimir Trifonov rất ư là “xui”. Số là cả Trifonov và Reingold đều có kết quả rất tốt cho bài toán tìm sự liên thông trên đồ thị vô hướng (undirected st-connectivity). Dĩ nhiên ta có thể dùng BFS/DFS để giải bài này, nhưng tổng bộ nhớ cần thiết là [Only registered and activated users can see links. ]. [Only registered and activated users can see links. ] (1970) nói rằng có thể giải bài này dùng [Only registered and activated users can see links. ]-bộ nhớ. Mấy mươi năm sau đó thì có vài kết quả tốt dần lên, cho đến [Only registered and activated users can see links. ] của Armoni–Ta-Shma–Wigderson–Zhou năm 1997. Trifonov [Only registered and activated users can see links. ] đến [Only registered and activated users can see links. ], còn Reingold chứng minh được [Only registered and activated users can see links. ] luôn. Trifonov xui là vì nếu không có kết quả của Reingold thì kết quả của Trifonov thật sự là một phát triển rất mạnh (từ log xuống log-log). Kết quả là Reingold được giải bài báo hay nhất, còn Trifonov được giải bài báo sinh viên hay nhất cho STOC 2005.
Để chuẩn bị kiến thức nền cho mấy bài tới, chúng ta lại làm thêm một chuyến de-tour nữa, sang món giải tích Fourier của các hàm nhị phân. Để giải trí, ta chứng minh định lý Arrow về tính duy lý của sự độc tài bằng phân tích Fourier.

9. Biểu diễn nhóm và biến đổi Fourier

9.1. Các ký tự bất khả qui của nhóm Abel hữu hạn
Trong [Only registered and activated users can see links. ] [Only registered and activated users can see links. ] về nhân ma trận đang viết dở, tôi đã tóm tắt lại một số kiến thức cơ bản về lý thuyết biểu diễn nhóm. Xem thêm [Only registered and activated users can see links. ] của HT THT. Ta sẽ thu thập lại vài kết quả cần thiết để dùng trong bài này và trong một bài tương lai khi ta phân tích cái expander của Margulis.
Các biểu diễn bất khả qui của một nhóm Abel bất kỳ đều là các biểu diễn với số chiều bằng một. Nếu nhóm có [Only registered and activated users can see links. ] phần tử thì có [Only registered and activated users can see links. ] ký tự trực giao. Nhóm tuần toàn là một nhóm Abel. Nhóm tuần hoàn [Only registered and activated users can see links. ] có đúng [Only registered and activated users can see links. ] ký tự (characters) [Only registered and activated users can see links. ]. Mỗi ký tự [Only registered and activated users can see links. ] là một vector trong không gian vector phức [Only registered and activated users can see links. ], định nghĩa là [Only registered and activated users can see links. ], trong đó [Only registered and activated users can see links. ]. Các ký tự này là một hệ trực chuẩn theo tích Hermit này:

[Only registered and activated users can see links. ]

[Only registered and activated users can see links. ] của các nhóm Abel hữu hạn cho ta biết một nhóm Abel [Only registered and activated users can see links. ] hữu hạn bất kỳ đều có thể viết dưới dạng tổng trực tiếp của các nhóm tuần hoàn: [Only registered and activated users can see links. ]. Các biểu diễn bất khả qui của nhóm [Only registered and activated users can see links. ] là [Only registered and activated users can see links. ] của các biểu diễn bất khả qui của các nhóm tuần hoàn [Only registered and activated users can see links. ]. Các ký tự bất khả qui của nhóm [Only registered and activated users can see links. ] là tích tăng sờ của các ký tự bất khả qui của các nhóm tuần hoàn [Only registered and activated users can see links. ]. Với mỗi [Only registered and activated users can see links. ], ta có một ký tự bất khả quy [Only registered and activated users can see links. ] của nhóm [Only registered and activated users can see links. ] định nghĩa như sau: với một “tọa độ” [Only registered and activated users can see links. ] thì

[Only registered and activated users can see links. ]

Một trường hợp đặc biệt của nhóm Abel hữu hạn rất quan trọng trong chuỗi bài này và trong KHMT nói chung là [Only registered and activated users can see links. ]. Có thể nghĩ về mỗi phần tử của [Only registered and activated users can see links. ] như một đỉnh của khối [Only registered and activated users can see links. ]-cube, hoặc là một phép gán sự thật (truth assignment) vào [Only registered and activated users can see links. ] biến, hoặc là một tập con [Only registered and activated users can see links. ] trong đó [Only registered and activated users can see links. ] là tập các tọa độ bằng [Only registered and activated users can see links. ] của phần tử. Ở đây, nhóm [Only registered and activated users can see links. ] có [Only registered and activated users can see links. ] phần tử, và vì thế [Only registered and activated users can see links. ] ký tự bất khả qui. Do [Only registered and activated users can see links. ], với mỗi cặp [Only registered and activated users can see links. ] ta có [Only registered and activated users can see links. ].
Thay vì dùng [Only registered and activated users can see links. ] để đánh chỉ số các ký tự và các tọa độ của chúng, ta có thể dùng các tập con [Only registered and activated users can see links. ] của [Only registered and activated users can see links. ] để đánh chỉ số, trong đó [Only registered and activated users can see links. ], và [Only registered and activated users can see links. ]. Theo cách này, bộ các ký tự có thể định nghĩa bằng [Only registered and activated users can see links. ]. Còn nếu chúng ta dùng [Only registered and activated users can see links. ] làm tọa độ thì [Only registered and activated users can see links. ]. Bạn nên làm quen với việc chuyển qua lại giữa các tập con của [Only registered and activated users can see links. ] và các vectors của [Only registered and activated users can see links. ].
Lý do chính chúng ta quan tâm đến các ký tự bất khả qui của nhóm [Only registered and activated users can see links. ] là như sau. Trong phân tích độ khó xấp xỉ, chúng ta thường quan tâm đến các hàm Bool (hàm nhị phân) gồm [Only registered and activated users can see links. ] biến nhị phân loại [Only registered and activated users can see links. ]. Mỗi hàm loại này có thể xem là một vector trong không gian [Only registered and activated users can see links. ]. Dĩ nhiên, chúng cũng là các vectors trong không gian [Only registered and activated users can see links. ] và [Only registered and activated users can see links. ]. Như đã nói ở trên, các ký tự bất khả qui là một cơ sở trực chuẩn của không gian [Only registered and activated users can see links. ]. Vì thế, một hàm nhị phân [Only registered and activated users can see links. ] biến bất kỳ, nếu viết thành một vector trong không gian [Only registered and activated users can see links. ], đều là tổ hợp tuyến tính của các ký tự bất khả qui.
Thay vì làm việc trên không gian vector [Only registered and activated users can see links. ], chúng ta cũng có thể làm việc trên không gian (tuyến tính) của hàm số [Only registered and activated users can see links. ]. Chúng tương đương với nhau. Hàm [Only registered and activated users can see links. ] bất kỳ đều có thể biểu diễn dưới dạng

[Only registered and activated users can see links. ]

Để cái đám [Only registered and activated users can see links. ] trên số mũ thì hơi khó chịu. Chúng ta đổi biến. Đặt [Only registered and activated users can see links. ]. Nghĩa là nếu [Only registered and activated users can see links. ] (FALSE) thì [Only registered and activated users can see links. ], còn [Only registered and activated users can see links. ] (TRUE) thì [Only registered and activated users can see links. ]. Thì mọi hàm [Only registered and activated users can see links. ] đều có thể viết dưới dạng

[Only registered and activated users can see links. ]

trong đó (lạm dụng ký hiệu một chút) [Only registered and activated users can see links. ] là một hàm đơn thức

[Only registered and activated users can see links. ]

Đám [Only registered and activated users can see links. ] bây giờ gọi là hệ cơ sở đơn thức (monomial basis) của các hàm [Only registered and activated users can see links. ]. Nhớ rằng cái hệ cơ sở đơn thức này là một hệ cơ sở trực chuẩn của không gian các hàm [Only registered and activated users can see links. ]. Trong đó, “tích vô hướng” của hai hàm [Only registered and activated users can see links. ] bất kỳ được định nghĩa là

[Only registered and activated users can see links. ]

trong đó trị kỳ vọng ở vế phải tính trên phân bố đều của các vectors [Only registered and activated users can see links. ]. Chúng ta sẽ thấy rằng hiểu tích vô hướng của hai hàm như trị kỳ vọng của tích rất hữu dụng về sau.

9.2. Biến đổi Fourier
Ý tưởng chính của biến đổi Fourier rời rạc chỉ là một phát biểu cơ bản của đại số tuyến tính: các vector trong một không gian vector đều là tổ hợp tuyến tính của một hệ cơ sở của không gian đó. (Xem thêm [Only registered and activated users can see links. ] giới thiệu về biến đổi Fourier. Một chương của [Only registered and activated users can see links. ] mới của bác Văn với Terry cũng giới thiệu cách dùng giải tích điều hòa — harmonic analysis — trong toán tổ hợp cộng tính — additive combinatorics.)
Trong ngữ cảnh của chúng ta, mỗi hàm [Only registered and activated users can see links. ] đều là tổ hợp tuyến tính của các hàm đơn thức:

[Only registered and activated users can see links. ]

Tổ hợp này là duy nhất. Các hệ số [Only registered and activated users can see links. ] gọi là các hệ số Fourier của [Only registered and activated users can see links. ]. Chúng là các số thực vì [Only registered and activated users can see links. ] và [Only registered and activated users can see links. ] là các vectors thực. Từ giờ trở đi chúng ta có thể làm việc luôn trên không gian [Only registered and activated users can see links. ] thay vì [Only registered and activated users can see links. ] và không cần cái liên hợp (conjugate) khi tính tích vô hướng của hai vectors nữa. Hệ cơ sở đơn thức [Only registered and activated users can see links. ] cũng được gọi là hệ cơ sở Fourier.
Hai đẳng thức cơ bản nhất của biến đổi Fourier là

• [Only registered and activated users can see links. ]
  [Only registered and activated users can see links. ]
• và trường hợp đặc biệt là [Only registered and activated users can see links. ]
  [Only registered and activated users can see links. ]

Bài tập. chứng minh hai đẳng thức trên từ định nghĩa và tính trực chuẩn của các [Only registered and activated users can see links. ].

10. Luật bầu cử và biến đổi Fourier cho các hàm nhị phân
Trong trường hợp hàm nhị phân [Only registered and activated users can see links. ] thì [Only registered and activated users can see links. ] với mọi [Only registered and activated users can see links. ], vì thế đẳng thức Parseval cho

[Only registered and activated users can see links. ]

Có thể nghĩ về một hàm nhị phân như một “luật” bầu cử. Có [Only registered and activated users can see links. ] phiếu bầu [Only registered and activated users can see links. ] cho hai ứng cử viên [Only registered and activated users can see links. ] và [Only registered and activated users can see links. ]. Hàm [Only registered and activated users can see links. ] trả về người thắng cử. Sau đây là một số hàm (luật) bầu cử hay thấy trên thực tế:

• [Only registered and activated users can see links. ] là hàm bầu đa số, chỉ định nghĩa với [Only registered and activated users can see links. ] lẻ, trả về [Only registered and activated users can see links. ] nếu đa số các “phiếu” là [Only registered and activated users can see links. ] và ngược lại.
• [Only registered and activated users can see links. ] là hàm độc tài (dictator) thứ [Only registered and activated users can see links. ], trả về phiếu bầu của [Only registered and activated users can see links. ], nghĩa là [Only registered and activated users can see links. ].
• [Only registered and activated users can see links. ] và [Only registered and activated users can see links. ] là các hàm hằng số (hay hàm “đảng cử, dân bầu”), luôn trả về giá trị đảng cử [Only registered and activated users can see links. ] hoặc [Only registered and activated users can see links. ].

Ta cũng có thể định nghĩa một số hàm khác như hàm chẵn lẻ, hàm “electoral college” (như trong luật bầu cử của Mỹ), vân vân. Xem [Only registered and activated users can see links. ] của Ryan O’Donnell để thêm một số ví dụ.
Với một luật bầu cử nhất định, chúng ta muốn biết nhiều thuộc tính của nó.

• Nó có thiên vị không? Thiên vị ở đây được hiểu như sau, nếu ta lấy một bộ [Only registered and activated users can see links. ] phiếu bầu ngẫu nhiên thì xác suất mà kết quả là [Only registered and activated users can see links. ] hoặc [Only registered and activated users can see links. ] khác nhau cỡ nào. Một luật bầu là “công bằng” nếu hai xác suất này bằng nhau. Do đó, ta định nghĩa sự thiên vị của hàm [Only registered and activated users can see links. ] bằng
  [Only registered and activated users can see links. ]
  Đến đây thì ta thấy phân tích Fourier có lợi thế nào. Do hàm [Only registered and activated users can see links. ], độ thiên vị của [Only registered and activated users can see links. ] là
  
  [Only registered and activated users can see links. ]
  Độ thiên vị của [Only registered and activated users can see links. ] chính là hệ số Fourier thứ nhất! Dễ thấy rằng các hàm đảng cử/dân bầu có thiên vị là [Only registered and activated users can see links. ]. Các hàm độc tài và hàm đa số có độ thiên vị bằng [Only registered and activated users can see links. ].
• Ảnh hưởng của một phiếu nào đó ra sao? Nếu Tám Tàng đổi phiếu từ [Only registered and activated users can see links. ] sang [Only registered and activated users can see links. ] thì kết quả bị đổi thế nào? Với bộ phiếu [Only registered and activated users can see links. ], gọi [Only registered and activated users can see links. ] là bộ phiếu mà ta đổi phiếu [Only registered and activated users can see links. ] lại. Thì tầm ảnh hưởng của phiếu thứ [Only registered and activated users can see links. ] trên kết quả được định nghĩa là
  [Only registered and activated users can see links. ]
  Trong lý thuyết chọn lựa xã hội (social choice theory) thì tầm ảnh hưởng này còn được gọi là [Only registered and activated users can see links. ] hoặc Banzhaf-Penrose index. Chỉ số này đã được dùng trong một vài phiên tòa về bầu cử. Các hệ số Fourier lại giúp ta:
  
  [Only registered and activated users can see links. ]
  (bài tập!)
  Dễ thấy rằng tầm ảnh hưởng của các hàm đảng cử là [Only registered and activated users can see links. ], tầm ảnh hưởng của hàm độc tài là [Only registered and activated users can see links. ] cho tất cả trừ anh độc tài có ảnh hưởng bằng [Only registered and activated users can see links. ]. Tầm ảnh hưởng của hàm đa số thì mất công hơn một chút. Dùng [Only registered and activated users can see links. ] ta tính được nó bằng khoảng [Only registered and activated users can see links. ].
• Ảnh hưởng của nhiễu ra sao? Khi ghi lại cả triệu phiếu bầu thì xác suất mà một phiếu bị ghi sai không bỏ qua được. Gọi xác suất này là [Only registered and activated users can see links. ] chẳng hạn. Giả sử ta lấy một bộ phiếu bầu [Only registered and activated users can see links. ] hoàn toàn ngẫu nhiên. Gọi [Only registered and activated users can see links. ] là bộ phiếu đạt được bằng cách lật mỗi phiếu [Only registered and activated users can see links. ] với xác suất [Only registered and activated users can see links. ]. Dễ thấy, với mọi [Only registered and activated users can see links. ],
  [Only registered and activated users can see links. ]
  Do đó cặp [Only registered and activated users can see links. ] được gọi là [Only registered and activated users can see links. ]-correlated. Độ ổn định nhiễu của [Only registered and activated users can see links. ] tại [Only registered and activated users can see links. ] được định nghĩa là
  
  [Only registered and activated users can see links. ]
  Ngược lại:
  
  [Only registered and activated users can see links. ]
  Ta cũng tính được độ ổn định nhiễu dùng các hệ số Fourier:
  
  [Only registered and activated users can see links. ]
  (bài tập!)
  Độ ổn định nhiễu của các hàm đảng cử là [Only registered and activated users can see links. ], của hàm độc tài thứ [Only registered and activated users can see links. ] là [Only registered and activated users can see links. ]. Độ ổn định nhiễu của hàm đa số là thú vị nhất. Có thể chứng minh được điều sau đây:
  
  [Only registered and activated users can see links. ]
  Nếu ta dùng xấp xỉ [Only registered and activated users can see links. ] (khá tốt khi [Only registered and activated users can see links. ] nhỏ) thì ta thấy rằng cái nhiễu [Only registered and activated users can see links. ] dẫn đến xác suất khoảng [Only registered and activated users can see links. ] là kết quả bầu cử bị thay đổi.

11. Định lý Arrow và tính duy lý của sự độc tài
[Only registered and activated users can see links. ] là một triết gia, nhà toán học, và nhà khoa học chính trị người Pháp sống ở thế kỷ 18. Năm 1785, ông viết bài “Essay on the Application of Analysis to the Probability of Majority Decisions” có ảnh hưởng sâu rộng đến lý thuyết chọn lựa xã hội, kinh tế học, và hiện nay đến các thuật toán xếp hạng quảng cáo của các công ty như Google, Yahoo, Microsoft. Condorcet là một trong những người đầu tiên mang (tính chặt chẽ của) toán học vào nghiên cứu khoa học xã hội. Ông tham gia cách mạng Pháp, viết vài quyển sách bất hủ ủng hộ cho tinh thần Khai Sáng. Ông bị bắt giam gần một năm, và mất trong tù. Nhiều khả năng là do tự uống thuốc độc.
Ông khám phá ra [Only registered and activated users can see links. ]. Đại để cái nghịch lý này như sau. Giả sử nhà nước cần đầu tư vào ngành đóng tàu (ĐT), cầu đường (CĐ), hoặc giáo dục (GD). Nhà nước làm trưng cầu dân ý. Mỗi người cho biết xếp hạng của riêng mình về tầm quan trọng của ba thứ này. Ví dụ, anh Tám Tàng bảo tôi nghĩ GD trước, rồi đến CĐ, rồi đến ĐT. Anh Bảy Xị cho một thứ tự khác, vân vân. Thì có khả năng là đa số mọi người xếp GD trên CĐ, đa số xếp CĐ trên ĐT, và đa số xếp ĐT trên GD. Đó là tính phi lý của chọn lựa xã hội. Khi biết cái nghịch lý Condorcet rồi, chúng ta đọc các thống kê xã hội cẩn thận hơn. Obama với McCain cãi nhau, đều lôi thống kê ra. Một ông bảo phải đầu tư cái này do đa số dân chúng ủng hộ cái này hơn cái kia, McCain bảo cái kia hơn cái nọ. Chúng ta nên nghĩ ngay đến khả năng vô lý của chọn lựa xã hội. Có khả năng cả Obama lẫn McCain đều đúng, nhưng đều vô lý.
Đến năm 1950, [Only registered and activated users can see links. ] (giải Nobel kinh tế 1972) viết một bài báo rất nổi tiếng về các luật bầu cử, trong đó ông chứng minh [Only registered and activated users can see links. ] nói rằng hàm độc tài là luật bầu cử duy nhất có tính “duy lý” tuyệt đối. Chúng ta sẽ chứng minh định lý Arrow bằng giải tích Fourier.
Để đơn giản (nhưng không mất tính tổng quát) ta giả sử xã hội có 3 đề mục A, B, C cần xếp hạng bằng bầu cử (GD-CĐ-ĐT, hoặc Obama-McCain-Nader, hoặc cơm-sữa-bia). Người thứ [Only registered and activated users can see links. ] bầu 3 phiếu: phiếu [Only registered and activated users can see links. ] chọn A hơn B ([Only registered and activated users can see links. ]) hoặc B hơn A ([Only registered and activated users can see links. ]), [Only registered and activated users can see links. ] chọn giữa B và C, và [Only registered and activated users can see links. ] chọn giữa C và A. Nếu anh nào xếp hạng vòng tròn (A hơn B, B hơn C, và C hơn A) thì anh ấy bị chập, không cho bầu. Do đó chúng ta giả sử là ba phiếu bầu [Only registered and activated users can see links. ] của người thứ [Only registered and activated users can see links. ] mang tính duy lý. Nói cách khác, bộ ba [Only registered and activated users can see links. ] là duy lý nếu và chỉ nếu chúng không cùng bằng [Only registered and activated users can see links. ] hoặc [Only registered and activated users can see links. ].
Như vậy, nếu có [Only registered and activated users can see links. ] người thì ta có ba vectors [Only registered and activated users can see links. ]. Từ ba vectors này, “luật” bầu cử sẽ phải tính xem xã hội xếp hạng A, B, C như thế nào, nghĩa là xã hội thích cái nào hơn giữa A và B, giữa B và C, và giữa C và A. Luật bầu cử sẽ phải thỏa mãn một số tiên đề nhất định:

• Tính nhất trí (còn gọi là hiệu suất Pareto): nếu mỗi người đều thích A hơn B thì xã hội cũng phải chọn A hơn B.
• Không độc tài: xếp hạng của xã hội không thể luôn giống hệt như xếp hạng của một anh Bảy Xị nào đó.
• Sự độc lập của các chọn lựa không liên quan (independence of irrelevant alternatives — IIA): việc xã hội xếp hạng A hơn B hay B hơn A thì độc lập với thứ hạng của anh C trong các chọn lựa cá nhân.
• Tính duy lý: xã hội không thể xếp hạng quẩn quanh theo vòng tròn (A hơn B, B hơn C, và C hơn A).

Arrow chứng minh rằng không có hàm nào thỏa cả bốn điều kiện trên, cho dù các cá nhân đều duy lý. (Bài báo của Arrow khá là dài dòng văn tự. Với mỗi giả thuyết, tiên đề, ông lại đá sang triết lý và vài kết quả trước đó.) Định lý của Arrow thật sự là một định lý mang tính tổ hợp, và có các [Only registered and activated users can see links. ].
Chúng ta sẽ chứng minh định lý Arrow bằng phân tích Fourier. Chứng minh này là [Only registered and activated users can see links. ].
Từ giả thiết IIA, ta kết luận rằng chọn lựa xã hội có thể đúc kết bằng ba hàm số [Only registered and activated users can see links. ], [Only registered and activated users can see links. ], và [Only registered and activated users can see links. ]. Hàm [Only registered and activated users can see links. ] cho ta biết xã hội thích A hơn hay B hơn, [Only registered and activated users can see links. ] xếp hạng B và C, và [Only registered and activated users can see links. ] xếp hạng C và A.
Từ tính nhất trí và tính duy lý, ta sẽ chứng minh rằng [Only registered and activated users can see links. ]. Tính duy lý nói rằng không thể tồn tại các vectors [Only registered and activated users can see links. ], mỗi bộ [Only registered and activated users can see links. ] đều duy lý, mà lại cho ra kết quả phi lý [Only registered and activated users can see links. ]. Xét bộ ba [Only registered and activated users can see links. ], và [Only registered and activated users can see links. ]. Do tính nhất trí ta có [Only registered and activated users can see links. ]. Như vậy [Only registered and activated users can see links. ] phải khác với [Only registered and activated users can see links. ]. Nghĩa là [Only registered and activated users can see links. ] với mọi [Only registered and activated users can see links. ]. Tương tự ta có [Only registered and activated users can see links. ] với mọi [Only registered and activated users can see links. ]. Do đó [Only registered and activated users can see links. ]. Tương tự ta có [Only registered and activated users can see links. ].
Bây giờ giả sử tồn tại hàm [Only registered and activated users can see links. ] sao cho, với bất kỳ bộ ba duy lý [Only registered and activated users can see links. ] nào, cái chọn lựa xã hội [Only registered and activated users can see links. ] cũng duy lý. Ta sẽ chứng minh rằng [Only registered and activated users can see links. ] phải là hàm độc tài. Với mỗi cá nhân [Only registered and activated users can see links. ], chọn bộ ba [Only registered and activated users can see links. ] ngẫu nhiên từ một trong 6 bộ ba duy lý [Only registered and activated users can see links. ], [Only registered and activated users can see links. ], [Only registered and activated users can see links. ], [Only registered and activated users can see links. ], [Only registered and activated users can see links. ], và [Only registered and activated users can see links. ]. Ta sẽ có một bộ ba vectors [Only registered and activated users can see links. ] duy lý. Xác suất mà [Only registered and activated users can see links. ] là duy lý phải bằng [Only registered and activated users can see links. ], nếu luật bầu cử [Only registered and activated users can see links. ] là duy lý trong mọi trường hợp.
Định nghĩa hàm [Only registered and activated users can see links. ] như sau. (NAE là “not all equal”.) [Only registered and activated users can see links. ] nếu và chỉ nếu [Only registered and activated users can see links. ]. Khai triển Fourier của hàm này là

[Only registered and activated users can see links. ]

Như vậy, xác suất mà [Only registered and activated users can see links. ] là duy lý sẽ bằng

[Only registered and activated users can see links. ]

Do [Only registered and activated users can see links. ] có vai trò như nhau, ta kết luận

[Only registered and activated users can see links. ]

Nhớ rằng trị kỳ vọng được tính từ cách lấy các bộ ba duy lý [Only registered and activated users can see links. ] như mô tả ở trên. Từ đó dễ thấy rằng [Only registered and activated users can see links. ] là một cặp [Only registered and activated users can see links. ]-correlated. Do đó

[Only registered and activated users can see links. ]

Để cho gọn, ta định nghĩa [Only registered and activated users can see links. ]. Nhớ rằng [Only registered and activated users can see links. ], do đó [Only registered and activated users can see links. ]. Do đó, xác suất mà [Only registered and activated users can see links. ] là duy lý bằng

[Only registered and activated users can see links. ]

Xác suất này chỉ có thể bằng [Only registered and activated users can see links. ] nếu [Only registered and activated users can see links. ] và [Only registered and activated users can see links. ] với mọi [Only registered and activated users can see links. ]. Nhưng [Only registered and activated users can see links. ] nếu và chỉ nếu [Only registered and activated users can see links. ] hoặc [Only registered and activated users can see links. ] với [Only registered and activated users can see links. ] nào đó. Nhưng [Only registered and activated users can see links. ] phải thỏa tính nhất trí, do đó [Only registered and activated users can see links. ]. Và đó là tính duy lý của sự độc tài.
Chứng minh định lý Arrow bằng phương pháp này không chỉ để cho vui. Chứng minh cũ của Arrow không cho chúng ta biết xác suất sự phí lý của chọn lựa xã hội là bao nhiêu. Phân tích Fourier cho chúng ta biết, nếu ta dùng hàm đa số, khi [Only registered and activated users can see links. ] tiến đến vô cùng thì xác suất có chọn lựa xã hội duy lý là

[Only registered and activated users can see links. ]

Con số [Only registered and activated users can see links. ] này gọi là số Guilbaud. Chúng ta không những biết nghịch lý Condorcet có thể xảy ra mà còn biết cả xác suất của nó. Còn nhiều điều hay ho nữa từ chứng minh này, nhưng để dịp khác. Bài tới ta bàn về cái PCP của Hastad.

__________________
Kiếm thì vô tình mà người lại hữu tình.