2009-09-24 35 views
33

Thuật toán tốt nhất để lấy một chuỗi các số nguyên dài (nói 100.000 của chúng) và trả về một phép đo trình tự ngẫu nhiên như thế nào?Đo lường ngẫu nhiên tốt và đơn giản

Hàm sẽ trả về một kết quả duy nhất, nói 0 nếu chuỗi không phải là tất cả ngẫu nhiên, tối đa, giả sử 1 nếu hoàn toàn ngẫu nhiên. Nó có thể cung cấp cho một cái gì đó ở giữa nếu trình tự là hơi ngẫu nhiên, ví dụ: 0,95 có thể là một chuỗi ngẫu nhiên hợp lý, trong khi 0,50 có thể có một số phần không ngẫu nhiên và một số phần ngẫu nhiên.

Nếu tôi là để vượt qua 100.000 chữ số đầu tiên của Pi đến chức năng, nó sẽ cho một số rất gần với 1. Nếu tôi thông qua trình tự 1, 2, ... 100.000 đến nó, nó sẽ trả về 0.

Bằng cách này, tôi có thể dễ dàng lấy 30 chuỗi số, xác định ngẫu nhiên mỗi con số và trả về thông tin về ngẫu nhiên tương đối của chúng.

Có con vật như vậy không?

+4

Điểm bắt đầu có thể có: http://en.wikipedia.org/wiki/Randomness_tests –

+10

Tôi ngạc nhiên khi thấy rằng thực sự có các thuật toán xác nhận có thể kiểm tra tính ngẫu nhiên. Có lẽ tôi có một định nghĩa ngẫu nhiên khác với bạn đang nói về, nhưng từ quan điểm logic thì điều này không thể toán học được. Ngay cả khi bạn vượt qua trong 100K chữ số đó là tất cả 4 của nó là hoàn toàn khả thi mà nó đã được tạo ra ngẫu nhiên. Đọc một số bài báo có vẻ như chúng được thiết kế nhiều hơn để đánh giá sự phân bố hơn so với sự ngẫu nhiên thực tế. – JohnFx

+3

Tìm thấy bài viết này (http://en.wikipedia.org/wiki/Statistical_randomness) giải thích sự khác biệt giữa ngẫu nhiên thống kê và sự thật đã xóa nó cho tôi. Thú vị ... – JohnFx

Trả lời

12

Có thể thực hiện theo cách này:

CAcert Phòng thí nghiệm nghiên cứu không a Random Number Generator Analysis.

Their results page đánh giá từng chuỗi ngẫu nhiên bằng 7 thử nghiệm (Entropy, khoảng cách ngày sinh, cấp độ ma trận, cấp độ ma trận 6x8, khoảng cách tối thiểu, hình cầu ngẫu nhiên và bóp). Mỗi kết quả thử nghiệm sau đó được mã hóa màu là một trong "Không có vấn đề", "Có khả năng xác định" và "Không ngẫu nhiên".

Vì vậy, một hàm có thể được viết chấp nhận một chuỗi ngẫu nhiên và thực hiện 7 thử nghiệm. Nếu bất kỳ của 7 bài kiểm tra là "Không ngẫu nhiên" thì hàm trả về 0. Nếu tất cả 7 bài kiểm tra là "Không có vấn đề", thì nó trả về 1. Nếu không, nó có thể trả về một số ở giữa dựa trên cách nhiều bài kiểm tra được đưa vào dưới dạng "Xác định tiềm năng".

Điều duy nhất còn thiếu trong giải pháp này là mã cho 7 bài kiểm tra.

+2

Trang kết quả đó là một kho báu của các trình tạo số giả ngẫu nhiên. Nó cũng cho thấy một số điểm khá cao cho các chữ số pi (tìm kiếm PiDigits). Tất nhiên, việc đánh giá các chữ số pi là "có khả năng không xác định" cho thấy một điểm yếu cơ bản trong thuật ngữ của chúng tôi. –

0

Theo Knuth, hãy đảm bảo bạn kiểm tra các bit có thứ tự thấp cho ngẫu nhiên, vì nhiều thuật toán thể hiện sự ngẫu nhiên khủng khiếp ở các bit thấp nhất.

18

Câu hỏi của bạn tự trả lời. "Nếu tôi vượt qua 100.000 chữ số đầu tiên của Pi cho hàm, nó sẽ cho một số rất gần 1", ngoại trừ các chữ số của Pi không phải là số ngẫu nhiên vì vậy nếu thuật toán của bạn không nhận ra một chuỗi rất cụ thể là không ngẫu nhiên sau đó nó không phải là rất tốt.

Vấn đề ở đây là có nhiều loại không ngẫu nhiên: - ví dụ: "121,351,991,7898651,12398469018461" hoặc "33,27,99,3000,63,231" hoặc thậm chí "14297141600464,14344872783104,819534228736,3490442496" chắc chắn không phải ngẫu nhiên.

Tôi nghĩ điều bạn cần làm là xác định các khía cạnh ngẫu nhiên quan trọng đối với bạn- phân phối, phân phối chữ số, thiếu các yếu tố chung, số lượng số nguyên tố mong muốn, số lượng và các số "đặc biệt" khác v.v. .

PS. Thử nghiệm ngẫu nhiên và nhanh chóng (và rất hiệu quả) của tệp tin ngẫu nhiên là tệp có kết thúc gần bằng cùng một kích thước sau khi bạn nén nó.

+0

Tôi băn khoăn làm thế nào bạn có thể nói rằng các chữ số của Pi hoặc không ngẫu nhiên. Có thể sự ngẫu nhiên của Pi trong 100 triệu chữ số đầu tiên có thể không hiệu quả đối với một số ứng dụng nhất định như mã hóa dữ liệu như một số máy phát ngẫu nhiên khác (Xem: http://www.sciencedaily.com/releases/2005/04/050427094258. htm), nhưng tôi chưa bao giờ thấy bất cứ điều gì đã từng tuyên bố các chữ số của Pi là không ngẫu nhiên. – lkessler

+2

+1 cho "xác định các khía cạnh ngẫu nhiên quan trọng đối với bạn". Nếu đó là ngẫu nhiên thì nó sẽ vượt qua các bài kiểm tra cho sự ngẫu nhiên; nhưng trò chuyện không nắm giữ - không có thử nghiệm nào có thể xác minh tính ngẫu nhiên, ví dụ, người ta có thể có mối tương quan rất mạnh giữa các phần tử xa nhau và người ta thường phải kiểm tra một cách rõ ràng cho điều này. Trong thực tế, tôi thích điều này rất nhiều Tôi sẽ viết nó như là câu trả lời của riêng tôi ... – tom10

+14

pi không phải là một chuỗi các chữ số ngẫu nhiên, một chuỗi các chữ số rất dài - dài và không chứa bất kỳ sự lặp lại đáng kể nào - nhưng nó luôn luôn là cùng một chuỗi. –

3

Điều bạn tìm kiếm không tồn tại, ít nhất là cách bạn mô tả nó ngay bây giờ.

Vấn đề cơ bản là:
Nếu đó là ngẫu nhiên thì nó sẽ vượt qua kiểm tra tính ngẫu nhiên; nhưng trò chuyện không nắm giữ - không có bài kiểm tra nào có thể xác minh tính ngẫu nhiên.

Ví dụ: người ta có thể có mối tương quan rất mạnh giữa các phần tử cách xa nhau và người ta thường phải kiểm tra một cách rõ ràng cho điều này. Hoặc người ta có thể có một phân phối bằng phẳng nhưng được tạo ra theo cách rất không ngẫu nhiên. Vv, v.v.

Cuối cùng, bạn cần quyết định những khía cạnh nào của tính ngẫu nhiên là quan trọng đối với bạn và kiểm tra những điều này (như James Anderson mô tả trong câu trả lời của ông). Tôi chắc chắn nếu bạn nghĩ về bất kỳ điều đó không rõ ràng làm thế nào để kiểm tra, mọi người ở đây sẽ giúp đỡ.

Btw, tôi thường tiếp cận vấn đề này từ phía bên kia: Tôi đưa ra một số dữ liệu tìm kiếm tất cả những gì tôi có thể thấy là hoàn toàn ngẫu nhiên, nhưng tôi cần xác định xem có mẫu nào ở đâu đó không. Rất không rõ ràng, nói chung.

7

Như những người khác đã chỉ ra, bạn không thể trực tiếp tính toán trình tự ngẫu nhiên nhưng có một số kiểm tra thống kê mà bạn có thể sử dụng để tăng sự tự tin của mình.

DIEHARD suite là chuẩn thực tế cho loại thử nghiệm này nhưng nó không trả về một giá trị đơn lẻ cũng không đơn giản.

ENT - A Pseudorandom Number Sequence Test Program, là một giải pháp thay thế đơn giản kết hợp 5 thử nghiệm khác nhau. Trang web giải thích cách hoạt động của từng thử nghiệm này.

Nếu bạn thực sự chỉ cần một giá trị duy nhất, bạn có thể chọn một trong 5 thử nghiệm ENT và sử dụng. Các Chi-Squared test có lẽ sẽ là tốt nhất để sử dụng, nhưng điều đó có thể không đáp ứng được định nghĩa đơn giản.

Hãy nhớ rằng một thử nghiệm đơn lẻ không tốt bằng cách chạy một số thử nghiệm khác nhau trên cùng một trình tự. Tùy thuộc vào thử nghiệm nào bạn chọn, sẽ đủ tốt để gắn cờ các chuỗi đáng ngờ là không ngẫu nhiên, nhưng có thể không thất bại đối với các chuỗi xuất hiện một cách bề ngoài ngẫu nhiên nhưng thực sự thể hiện một số mẫu.

2

Trong màn hình máy tính Khi phân tích kết cấu, vấn đề cố gắng đánh giá mức độ ngẫu nhiên của một họa tiết xuất hiện, để phân đoạn nó. Điều này hoàn toàn giống với câu hỏi của bạn, bởi vì bạn đang cố gắng xác định sự ngẫu nhiên của một chuỗi các byte/số nguyên/phao. Thảo luận tốt nhất tôi có thể tìm thấy entropy hình ảnh là http://www.physicsforums.com/showthread.php?t=274518.

Về cơ bản, số đo thống kê ngẫu nhiên cho một chuỗi giá trị.

Tôi cũng sẽ thử tự tương quan với trình tự. Trong kết quả tự tương quan, nếu không có đỉnh nào khác với giá trị đầu tiên có nghĩa là không có chu kỳ đầu vào của bạn.

8

Bạn có thể cố nén nén chuỗi. Bạn càng thành công thì trình tự ngẫu nhiên càng ít.

Do đó, ngẫu nhiên heuristic = độ dài mã zip/độ dài của chuỗi gốc

+0

Đó là một ý tưởng thú vị. – lkessler

+1

Cảm ơn, tôi đã được truyền cảm hứng bởi sự phức tạp của Kolmogorov. Theo Kolmogorov một chuỗi là ngẫu nhiên nếu nó không thể được tạo ra bởi một thuật toán ngắn hơn dãy. Ví dụ, PI không phải ngẫu nhiên vì nó có thể được tạo ra bởi một thuật toán ngắn. – ragnarius

+0

@ragnarius khoảng 100 mb chữ số pi nén xuống 45%. Vì vậy, theo định nghĩa của bạn khoảng 45% ngẫu nhiên của nó? : D – data

3

"Chuỗi này là ngẫu nhiên như thế nào?" là một câu hỏi khó bởi vì về cơ bản bạn quan tâm đến cách trình tự được tạo ra. Như những người khác đã nói rằng nó hoàn toàn có thể để tạo ra các chuỗi xuất hiện ngẫu nhiên, nhưng không đến từ các nguồn mà chúng tôi muốn xem xét ngẫu nhiên (ví dụ như chữ số của pi).

Hầu hết các kiểm tra ngẫu nhiên tìm cách trả lời một câu hỏi hơi khác nhau, đó là: "Chuỗi này có dị thường đối với một mô hình cụ thể không?".Nếu bạn là mô hình đang lăn xúc xắc mười mặt, sau đó nó rất dễ dàng để định lượng khả năng một chuỗi được tạo ra từ mô hình đó, và các chữ số của pi sẽ không nhìn bất thường. Nhưng nếu mô hình của bạn là "Chuỗi này có thể dễ dàng được tạo ra từ một thuật toán không?" nó trở nên khó khăn hơn nhiều.

+0

Không, tôi thực sự yêu cầu điều này: Tôi đã có một loạt các con số. Làm thế nào ngẫu nhiên là loạt? Tôi có thể không biết hoặc không thực sự quan tâm nó được tạo ra như thế nào. Tôi chỉ muốn biết nếu nó là ngẫu nhiên hay không. – lkessler

+3

Quan điểm của tôi là bạn phải xác định ngẫu nhiên với một số loại mô hình. – job

4

Bạn có thể xử lý 100.000 kết quả đầu ra như là kết quả có thể có của một biến ngẫu nhiên và tính toán entropy liên quan của nó. Nó sẽ cho bạn một thước đo về sự không chắc chắn. (Tiếp theo hình ảnh là từ wikipedia và bạn có thể tìm thêm thông tin về Entropy ở đó.) Đơn giản chỉ cần:

Entropy formula

Bạn chỉ cần để tính toán tần số của mỗi số trong dãy. Điều đó sẽ cho bạn p (xi) (ví dụ: nếu 10 xuất hiện 27 lần p (10) = 27/L trong đó L là 100.000 cho trường hợp của bạn.) Điều này sẽ cung cấp cho bạn thước đo entropy.

Mặc dù nó sẽ không cung cấp cho bạn một số từ 0 đến 1. Tuy nhiên 0 sẽ không chắc chắn tối thiểu. Tuy nhiên giới hạn trên sẽ không được 1. Bạn cần phải bình thường hóa đầu ra để đạt được điều đó.

+1

Đây chắc chắn là ý tưởng đúng đắn! +1 – lkessler

+1

Hmmmm ....Vậy entropy của 111111111122222222223333333333444444444455555555556666666666777777777788888888889999999999 là gì? – tom10

+1

Điểm tốt, Tom. Bản thân Entropy sẽ không hoạt động. – lkessler

2

@JohnFx "... toán học không thể."

bang poster: mất một chuỗi dài các số nguyên ...

Do đó, cũng giống như giới hạn này được sử dụng trong The Calculus, chúng ta có thể lấy giá trị như là giá trị - các nghiên cứu về Chaotics cho chúng ta thấy giới hạn hữu hạn có thể 'tự bật lên' tạo ra các trường tensor cung cấp ảo tưởng về (các) tuyệt đối và có thể chạy miễn là có thời gian và năng lượng. Do độ cong của không-thời gian, không có sự hoàn hảo - do đó op của "... nói 1 nếu hoàn toàn ngẫu nhiên." là một từ sai.

{lưu ý: quan sát phong phú trên đã được cung cấp - tha cho tôi}

Theo vị trí của bạn, đưa ra hai byte [] của một vài k, mỗi ngẫu nhiên độc lập - op không thể có được "một phép đo về cách ngẫu nhiên trình tự là "Bài báo tại Wiki là thông tin, và làm cho các bước tiến rõ ràng không phân tán vấn đề, nhưng

So với vật lý cổ điển, vật lý lượng tử dự đoán rằng các thuộc tính của hệ thống cơ học lượng tử phụ thuộc vào phép đo ngữ cảnh, tức là có thực hiện các phép đo hệ thống khác hay không.

Một nhóm các nhà vật lý từ Innsbruck, Áo , do Christian Roos và Rainer Blatt, có lần đầu tiên được chứng minh trong một thí nghiệm toàn diện rằng nó không thể giải thích hiện tượng lượng tử trong không theo ngữ cảnh điều khoản.

Nguồn: Khoa học hàng ngày

Chúng ta hãy xem xét phong trào thằn lằn không ngẫu nhiên. Nguồn gốc của các kích thích kinh tế bắt đầu các chuyển động phức tạp trong những cái đuôi của những con tắc kè báo, dưới siêu gốc, sửa chữa luận án của bạn, không bao giờ có thể được biết đến. Chúng ta, những nhà khoa học máy tính có kinh nghiệm, chịu đựng thử thách ngây thơ do những người mới biết đến quá rõ rằng ở đó - trong bối cảnh của một tâm trí không bị nhiễm độc và nguyên sơ - là những viên đá quý và người tạo mầm của tư tưởng hướng về phía trước.

Nếu trường suy nghĩ của con thằn lằn gốc tạo ra trường tensor (đối phó với nó, đây là nghiên cứu tiền tuyến trong vật lý tuyến tính) thì chúng ta có thể có "thuật toán tốt nhất để có chuỗi dài" các nền văn minh trải dài từ sự kiện Toba để trình bày thông qua một Inversion Chaotic "Hãy xem xét câu hỏi liệu một ý nghĩ trường như vậy được tạo ra bởi con thằn lằn, lấy một cách độc lập, là một ma quái hoặc có thể biết được.

" Quan sát trực tiếp của nghịch lý Hardy bằng phép đo yếu khớp với một cặp photon vướng víu , "tác giả Kazuhiro Yokota, Takashi Yamamoto, Masato Koashi và Nobuyuki Imoto từ các Graduate School of Engineering Khoa học tại Đại học Osaka và Dự án Thông tin Quantum CREST Photonic trong Kawaguchi Thành phố

Nguồn: Khoa học hàng ngày

(xem xét các ma quái/phân đôi có thể biết được)

Tôi biết từ các thí nghiệm của riêng mình rằng việc quan sát trực tiếp làm suy yếu tính tuyệt đối của các dây dẫn cảm nhận được, phân biệt giữa các thiết bị có thể sử dụng các kỹ thuật lấy nét đơn vì hàng rào cảm nhận được không phải là ý nghĩ ban đầu. Một hệ quả cơ bản của Quantaeus là các trạng thái yếu của các tensors dễ nhận biết có thể phân biệt một cách đáng tin cậy với nhau mà không gây ra sự sụp đổ thành một tensor cảm nhận thống nhất. Hãy thử nó đôi khi - làm việc trên sự chính xác của một số tình huống mong muốn, bằng cách sử dụng tư tưởng thuần túy. Bởi vì một ý tưởng không có thời gian hay không gian nên nó không có giá trị. (không hữu hạn) và do đó có thể đạt được "sự hoàn hảo" - nghĩa là sự tuyệt đối. Chỉ cần cho một gợi ý, bắt đầu với thời tiết vì đó là điều dễ ảnh hưởng nhất (ít nhất là hiện nay), sau đó di chuyển càng sớm càng tốt để thực hiện một phép nối từ trạng thái ngủ đến trạng thái thức với hầu như không bị gián đoạn chuỗi liên tiếp.

Có một đốm sáng gần như không thể tránh khỏi khi cơ thể thức dậy nhưng nó giống như khi chuông cửa reo, nói đến điều đó mang lại một lĩnh vực nghiên cứu thống kê thú vị để cấp vốn: Có bao nhiêu ý nghĩ duy trì đồng bộ? Tôi thấy rằng tính hai mặt là giới hạn làm việc thực tế, tại triune nó hoặc là phá vỡ những suy nghĩ tiếp theo hoặc không kéo dài quá lâu.

Có lẽ công việc của Yokota và cộng sự có thể tiết lộ nguồn gốc của lưu lượng truy cập giả mạo ... có lẽ đó là ma.

+2

. . . . . . . . . Gì? –

Các vấn đề liên quan