Giới thiệu về một số thử nghiệm trong NIST SP 800-22 rev 1a và chức năng erfc

pioneer

06:40, 19/07/2023

Tôi đang tìm hiểu bài kiểm tra tính ngẫu nhiên của tài liệu NIST SP 800-22 rev 1a.

https://csrc.nist.gov/publications/detail/sp/800-22/rev-1a/final

Khi tôi đang đọc, một vài câu hỏi xuất hiện và tôi đặt chúng như thế này. Câu hỏi của tôi là:

Trong Kiểm tra tần suất trong Khối 2.2, nhìn vào (3) của 2.2.4, có một phần được tính như sau. $$\chi^2(obs)=4M\sum_{i=1}^{N}(\pi_i - 1/2)^2$$ Tôi không hiểu tại sao nó lại nhân với 4 ở đây.
Trong Kiểm tra số lần chạy 2.3, giá trị p được tính như sau $$P-value = erfc(\frac{|V_n(obs)-2n\pi(1-\pi)|}{2\sqrt{2n}\pi(1-\pi)}).$$ Giá trị của mẫu số ở đây là gì? tôi biết điều đó $2\pi(1-\pi)$ là trung bình, nhưng tôi không biết mẫu số đến từ đâu.
Có lý do nào để tìm giá trị p thông qua erf thay vì phân phối chuẩn trong (2) không?

Cảm ơn bạn.

0 + 0

ngẫu nhiên

Điểm:0

Crypto

Daniel S

09:09, 19/07/2023

Điều này thật đáng lo ngại. Thông thường lề $\chi^2$ kiểm tra sẽ là $$M\sum_{i=1}^n\frac{\left(\pi_i-\frac12\right)^2}{\frac12}=2M\sum_{i=1}^n\left(\pi_i- \frac12\right)^2.$$ Tôi sẽ suy nghĩ thêm, nhưng có thể đáng để chuyển các tầng ngậm nước sang NIST.
Nó được cho là độ lệch chuẩn. Đối với các bit độc lập, được phân phối giống hệt nhau, thống kê chạy phải được phân phối nhị thức. Định lý giới hạn trung tâm sau đó cho chúng ta biết rằng nhị thức có thể xấp xỉ với phân phối chuẩn. Tuy nhiên, lưu ý rằng dấu căn bậc hai sẽ mở rộng trên $\pi(1-\pi)$ hệ số.
Hàm erf tính toán phân phối chuẩn hai phía. Chúng tôi quan tâm đến cả hai trường hợp chạy phổ biến (nghĩa là có nhiều cặp 00 và 11 liên tiếp) và trường hợp chúng bị thiếu (tức là có nhiều cặp 01 và 10). Cả hai đều cho thấy các vấn đề với việc phân phối, nhưng được giải thích bằng các đuôi ngược lại.

0 + 0

pioneer

10:39, 19/07/2023

Cảm ơn vì đã trả lời. Nhưng tôi không hoàn toàn hiểu câu trả lời thứ hai. Nếu tôi viết biểu thức như bạn nói, $p-value$ không nên là $erfc(\frac{|V_n(obs)-n\pi|}{\sqrt{n\pi(1-\pi)}} )$?vì đối với CLT, tôi cần xây dựng biểu thức $\frac{V_n-np}{\sqrt{npq}}$.

Hồi đáp

Daniel S

11:13, 19/07/2023

Thống kê của bạn sẽ chính xác để kiểm tra số lượng 1 ($\pi$ là xác suất xuất ra 1). Họ đang đếm số 01 và 10. Những điều này xảy ra với xác suất $(1-\pi)\pi$ và $\pi(1-\pi)$ nên chúng ta có $\mathrm{Bin}(n-1,2\pi(1-\pi) ) $ phân phối. Nhìn sâu hơn, dường như có một số gần đúng kỳ lạ đang diễn ra.May mắn thay, tài liệu này đang được sửa đổi, vì vậy có thể có cơ hội làm sáng tỏ mọi thứ trong phiên bản mới.

Hồi đáp

pioneer

11:31, 19/07/2023

Như bạn đã đề cập, có thể hiểu rằng $V_n(obs)$~$Bin(n-1, 2\pi(1-\pi))$ hài lòng vì họ đếm số lượng 10 và 01. Tuy nhiên, vì ngay cả trường hợp như vậy cũng thỏa mãn biểu thức $P-value = erfc(\frac{|V_n(obs)-2n\pi(1-\pi)|}{\sqrt{n2\pi(1-\pi)( 1-2\pi(1-\pi))}}).$, biểu thức trong tài liệu không thỏa mãn. Là biểu thức trong tài liệu sai? (+Thực ra nên viết là $n-1$ thay vì $n$, đổi tùy ý có được không?)

Hồi đáp

Daniel S

12:04, 19/07/2023

Tôi ngần ngại khẳng định tính không chính xác vì họ có thể đang sử dụng một số phép tính gần đúng với phương sai mà tôi không biết. Lưu ý rằng biểu thức erf của bạn yêu cầu $\sqrt 2$ ở mẫu số. Lỗi khi chuyển từ $n-1$ sang $n$ là không đáng kể khi $n$ phát triển. Tôi nghĩ rằng đáng để nêu vấn đề này và truy vấn đầu tiên của bạn với NIST nếu các biểu thức vẫn xuất hiện trong phiên bản sửa đổi và tôi sẽ cố gắng làm như vậy.

Hồi đáp

pioneer

12:34, 19/07/2023

Tôi hiểu rồi. Thời gian tới, tôi hy vọng rằng NIST sẽ sửa đổi các sự kiện này cho đúng hoặc xuất bản một tài liệu với các giải thích đầy đủ về vấn đề này. Cảm ơn bạn rất nhiều vì câu trả lời tốt.

Hồi đáp

Phan Văn Trường

Câu hỏi này là trong các ngôn ngữ khác:

EN: About some tests in NIST SP 800-22 rev 1a and erfc function

TH: เกี่ยวกับการทดสอบบางอย่างในฟังก์ชัน NIST SP 800-22 rev 1a และ erfc

RO: Despre unele teste în NIST SP 800-22 rev 1a și funcția erfc

RU: О некоторых тестах в NIST SP 800-22 rev 1a и функции erfc

VI: Giới thiệu về một số thử nghiệm trong NIST SP 800-22 rev 1a và chức năng erfc

Đăng câu trả lời

Hầu hết mọi người không hiểu rằng việc đặt nhiều câu hỏi sẽ mở ra cơ hội học hỏi và cải thiện mối quan hệ giữa các cá nhân. Ví dụ, trong các nghiên cứu của Alison, mặc dù mọi người có thể nhớ chính xác có bao nhiêu câu hỏi đã được đặt ra trong các cuộc trò chuyện của họ, nhưng họ không trực giác nhận ra mối liên hệ giữa câu hỏi và sự yêu thích. Qua bốn nghiên cứu, trong đó những người tham gia tự tham gia vào các cuộc trò chuyện hoặc đọc bản ghi lại các cuộc trò chuyện của người khác, mọi người có xu hướng không nhận ra rằng việc đặt câu hỏi sẽ ảnh hưởng—hoặc đã ảnh hưởng—mức độ thân thiện giữa những người đối thoại.