عشوائية بالكاد عشوائية في كل شيء ؟

Question

لقد فعلت ذلك لاختبار العشوائية randint:

>>> from random import randint
>>>
>>> uniques = []
>>> for i in range(4500):  # You can see I was optimistic.
...     x = randint(500, 5000)
...     if x in uniques:
...         raise Exception('We duped %d at iteration number %d' % (x, i))
...     uniques.append(x)
...
Traceback (most recent call last):
  File "<stdin>", line 4, in <module>
Exception: We duped 887 at iteration number 7

حاولت حوالي 10 مرات أكثر و أفضل نتيجة حصلت 121 التكرار قبل مكرر.هذا هو أفضل نوع من النتيجة التي يمكن الحصول عليها من المكتبة القياسية?

Answer 1

عيد ميلاد المفارقة ، أو لماذا PRNGs تنتج مكررة في كثير من الأحيان مما كنت قد يعتقد.

وهناك زوجين من القضايا في اللعب في OP المشكلة.واحد هو عيد ميلاد مفارقة كما ذكر أعلاه والثاني هو طبيعة ما يتم توليد ، وهو في حد ذاته لا يضمن عدد معين لن تتكرر.

عيد ميلاد مفارقة ينطبق حيث تعطى القيمة يمكن أن تحدث أكثر من مرة خلال الفترة من مولد - وبالتالي التكرارات يمكن أن يحدث داخل عينة من القيم.تأثير ميلاد المفارقة هي أن احتمال الحصول على مثل هذه التكرارات مهم جدا و متوسط الفترة بينهما هو أصغر من واحد قد يكون على خلاف ذلك الفكر.هذا التنافر بين والفعلية الاحتمالات يجعل عيد ميلاد مفارقة مثال جيد التحيز المعرفي, حيث ساذجة بديهية تقدير من المرجح أن يكون بعنف الخطأ.

لمحة سريعة عن شبه عشوائية عدد المولدات (PRNGs)

الجزء الأول من المشكلة هو أن يتم أخذ يتعرض قيمة مولد رقم عشوائي و تحويله إلى عدد أصغر بكثير ، وبالتالي فإن مساحة من القيم الممكنة هو انخفاض.على الرغم من أن بعض شبه عشوائية عدد المولدات عدم تكرار القيم خلال فترة التحول هذه التغييرات المجال أصغر واحد.أصغر المجال يبطل 'لا يكرر' شرط لذلك يمكنك أن تتوقع كبير احتمال تكرار.

بعض الخوارزميات مثل الخطية congruential PRNG (A'=AX|M) هل ضمان تفرد للفترة بأكملها.في LCG ولدت القيمة يحتوي على الدولة بأكملها من المجمع ولا إضافية الدولة هو عقد.المولد القطعية ولا يمكن تكرار الرقم في غضون الفترة - أي تراكم قيمة يمكن أن يعني واحد فقط ممكن المتعاقبة القيمة.ولذلك كل قيمة يمكن أن تحدث إلا مرة واحدة خلال فترة المولد.ومع ذلك ، الفترة هذه اللوائح هي صغيرة نسبيا - حوالي 2^30 نموذجية تطبيقات خوارزمية LCG - و لا يمكن أن يكون أكبر من عدد القيم المختلفة.

ليس كل اللوائح خوارزميات مشاركة هذه مميزة ؛ بعض يمكن تكرار قيمة معينة خلال هذه الفترة.في OP المشكلة ، ميرسين الاعصار خوارزمية (المستخدمة في بايثون عشوائية وحدة) وقد فترة طويلة جدا - أكبر بكثير من 2^32.على عكس خطي Congruential اللوائح ، والنتيجة ليست مجرد وظيفة من الناتج السابق قيمة المجمع يحتوي على دولة إضافية.مع 32 بت الناتج عدد صحيح و فترة ~2^19937 ، فإنه لا يمكن أن توفر مثل هذا الضمان.

في ميرسين الاعصار شعبية خوارزمية PRNGs لأنه لديه إحصائية جيدة و هندسية خصائص فترة طويلة جدا - الخصائص المرغوبة بالنسبة PRNG المستخدمة في نماذج المحاكاة.

• جيد إحصائية خصائص يعني أن الأرقام التي تم إنشاؤها بواسطة خوارزمية توزع بالتساوي مع عدم وجود أرقام أعلى بكثير من احتمال تظهر أكثر من غيرها.الفقراء الإحصائية خصائص يمكن أن تنتج غير المرغوب فيها انحراف في النتائج.

• جيد هندسية properies يعني أن مجموعات من N الأرقام لا تكذب على hyperplane في الابعاد الفضاء.الفقراء الخصائص الهندسية يمكن أن تولد زائفة الارتباطات في نموذج محاكاة وتشويه النتائج.

• فترة طويلة يعني أنك يمكن أن تولد الكثير من الأرقام قبل تسلسل يلتف حول بدء.إذا كان نموذج يحتاج إلى عدد كبير من التكرارات أو لابد من تشغيل العديد من البذور ثم 2^30 أو حتى منفصلة الأرقام المتاحة من نموذجي LCG التنفيذ قد لا تكون كافية.على MT19337 خوارزمية له فترة طويلة جدا - 2^19337-1 ، أو حوالي 10^5821.من خلال المقارنة, إجمالي عدد الذرات في الكون يقدر بنحو 10^80.

32-بت عدد صحيح المنتجة من MT19337 اللوائح لا يمكن أن تمثل ما يكفي من القيم المنفصلة لتجنب تكرار خلال هذه الفترة كبيرة.في هذه الحالة قيم مكررة من المحتمل أن تحدث و لا مفر منه مع كبير بما فيه الكفاية العينة.

عيد ميلاد مفارقة باختصار

هذه المشكلة هي في الأصل بأنها احتمال أي شخصين في غرفة تبادل عيد الميلاد نفسه.النقطة الرئيسية هي أن أي اثنين الناس في الغرفة يمكن أن حصة عيد ميلاد.الناس يميلون إلى بسذاجة تسيء المشكلة احتمال من شخص في غرفة تبادل عيد ميلاد مع شخص معين ، الذي هو مصدر التحيز المعرفي هذا غالبا ما يسبب الناس أن نقلل من احتمال.هذا هو افتراض غير صحيح - لا يشترط المباراة إلى شخص معين و أي شخصين يمكن أن المباراة.

احتمال من المباراة التي تحدث بين أي شخصين هو أعلى بكثير من احتمال من مباراة إلى شخص محدد كما المباراة لا يجب أن يكون إلى تاريخ محدد.بدلا من ذلك, لديك فقط للعثور على اثنين من الأفراد الذين يشتركون في نفس تاريخ الميلاد.من هذا الرسم البياني (التي يمكن العثور عليها على صفحة ويكيبيديا حول هذا الموضوع) ، يمكننا أن نرى أننا بحاجة فقط 23 شخصا في الغرفة ولكي تكون هناك فرصة 50 ٪ من العثور على اثنين من هذه المباراة في هذا السبيل.

من ويكيبيديا حول هذا الموضوع يمكننا الحصول على جميل ملخص. في OP مشكلة لدينا 4,500 ممكن أعياد الميلاد' بدلا من 365.لعدد معين من القيم العشوائية المولدة (ما يعادل 'الناس') نريد أن نعرف احتمال أي اثنين متطابقة القيم التي تظهر في تسلسل.

الحوسبة الأثر المحتمل مفارقة عيد ميلاد على المرجع مشكلة

عن سلسلة من 100 الأرقام لدينا أزواج (انظر فهم المشكلة) التي يمكن أن تتطابق مع (أيالأول يمكن أن تتطابق مع الثاني والثالث الخ ، الثاني أن مباراة الثالث والرابع الخ.وهلم جرا) ، وبالتالي فإن عدد تركيبات التي يمكن أن يحتمل أن تكون المباراة أكثر من 100.

من حساب الاحتمال نحصل على تعبير .التالي مقتطف من الثعبان رمز أدناه لا ساذجة تقييم احتمال مطابقة زوج الحدوث.

# === birthday.py ===========================================
#
from math import log10, factorial

PV=4500          # Number of possible values
SS=100           # Sample size

# These intermediate results are exceedingly large numbers;
# Python automatically starts using bignums behind the scenes.
#
numerator = factorial (PV)          
denominator = (PV ** SS) * factorial (PV - SS)

# Now we need to get from bignums to floats without intermediate
# values too large to cast into a double.  Taking the logs and 
# subtracting them is equivalent to division.
#  
log_prob_no_pair = log10 (numerator) - log10 (denominator)

# We've just calculated the log of the probability that *NO*
# two matching pairs occur in the sample.  The probability
# of at least one collision is 1.0 - the probability that no 
# matching pairs exist.
#
print 1.0 - (10 ** log_prob_no_pair)

هذا ينتج من المعقول يبحث نتيجة p=0.669 للمباراة التي تحدث في غضون 100 أرقام عينات من عدد سكانها 4500 القيم الممكنة.(ربما شخص ما يمكن أن تحقق هذا ومرحلة ما بعد تعليق إذا كان من الخطأ).من هذا يمكننا أن نرى أن أطوال يمتد بين الأرقام مطابقة لاحظ المرجع تبدو معقولة جدا.

حاشية:باستخدام خلط الحصول على فريدة من نوعها تسلسل الزائفة أرقام عشوائية

انظر هذا الجواب أدناه من S.مارك عن وسيلة للحصول على مضمونة فريدة من نوعها مجموعة من الأرقام العشوائية.تقنية ملصق يشير إلى أن يأخذ مجموعة من الأرقام (التي كنت العرض ، لذلك يمكنك جعلها فريدة من نوعها) و المراوغات لهم في ترتيب عشوائي.رسم الأرقام في تسلسل من أسكن مجموعة سوف تعطيك سلسلة من شبه عشوائي الأرقام التي تكفل عدم تكرار.

حاشية:آمن مشفر PRNGs

MT الخوارزمية ليست آمن مشفر كما أنه من السهل نسبيا أن نستنتج الدولة الداخلي من مولد خلال مراقبة سلسلة من الأرقام.خوارزميات أخرى مثل بلوم بلوم شب تستخدم التطبيقات المشفرة. ولكن قد تكون غير مناسبة محاكاة أو العامة رقم عشوائي التطبيقات.آمن مشفر PRNGs قد تكون مكلفة (ربما تتطلب bignum الحسابات) أو قد لا يكون لديك جيدة الخصائص الهندسية.في حالة من هذا النوع من الخوارزمية ، الشرط الأساسي هو أنه يجب أن يكون حسابيا متعذرا أن نستنتج الدولة الداخلي من مولد خلال مراقبة سلسلة من القيم.

Answer 2

قبل إلقاء اللوم على Python ، يجب عليك حقًا زيادة بعض نظرية الاحتمالات والإحصائيات. ابدأ بالقراءة عن مفارقة عيد ميلاد

بالمناسبة ، random الوحدة النمطية في Python تستخدم Mersenne Twister PRNG ، التي تعتبر جيدة جدًا ، لها فترة هائلة وتم اختبارها على نطاق واسع. لذا كن مطمئنًا أنك في أيد أمينة.

Answer 3

إذا كنت لا تريد واحدة متكررة ، فقم بإنشاء صفيف متسلسل واستخدام عشوائي

Answer 4

كإجابة على إجابة Nimbuz:

http://xkcd.com/221/

Answer 5

تتضمن العشوائية الحقيقية بالتأكيد تكرار القيم قبل أن يتم استنفاد مجموعة القيم المحتملة الكاملة. لن يكون الأمر عشوائيًا بخلاف ذلك ، حيث ستتمكن من التنبؤ بمدى عدم تكرار القيمة.

إذا كنت قد توفيت بالنرد ، فمن المؤكد أنك حصلت على 3 ستة ستة على صف في كثير من الأحيان ...

Answer 6

التنفيذ العشوائي لـ Python هو في الواقع أحدث ما يلي:

• http://en.wikipedia.org/wiki/Mersenne_twister
• http://docs.python.org/library/random.html

Answer 7

هذا ليس مكررًا. المكرر هو عندما تكرر نفس الشيء تسلسل. ليس فقط رقم واحد.

Answer 8

أنت تولد 4500 أرقام عشوائية من نطاق 500 <= x <= 5000. ثم تحقق لمعرفة كل رقم ما إذا كان قد تم إنشاؤه من قبل. ال مشكلة عيد الميلاد يخبرنا ما هو احتمال أن يتطابق اثنان من هذه الأرقام n يحاول الخروج من النطاق d.

يمكنك أيضًا عكس الصيغة لحساب عدد الأرقام التي يجب أن تنشئها حتى تكون فرصة توليد نسخة مكررة أكثر من 50%. في هذه الحالة لديك >50% فرصة لإيجاد رقم مكرر بعد 79 التكرارات.

Answer 9

لقد حددت مساحة عشوائية تبلغ 4501 قيمًا (500-5000) ، وأنت تكرر 4500 مرة. أنت مضمون بشكل أساسي للحصول على تصادم في الاختبار الذي كتبته.

للتفكير في الأمر بطريقة أخرى:

• عندما تكون صفيف النتيجة فارغة p (dupe) = 0
• 1 قيمة في Array P (dupe) = 1/4500
• 2 قيم في Array P (dupe) = 2/4500
• إلخ.

لذلك بحلول الوقت الذي تصل فيه إلى 45/4500 ، فإن هذا الإدراج لديه فرصة بنسبة 1 ٪ لتكون مكررة ، وهذا الاحتمال يستمر في الزيادة مع كل إدراج لاحق.

لإنشاء اختبار يختبر حقًا قدرات الوظيفة العشوائية ، قم بزيادة عالم القيم العشوائية المحتملة (على سبيل المثال: 500-500000) قد تحصل عليها أو لا تحصل عليها. لكنك ستحصل على المزيد من التكرارات في المتوسط.

Answer 10

لأي شخص آخر مع هذه المشكلة ، استخدمت uuid.uuid4 () ويعمل مثل السحر.

Answer 11

هناك مفارقة عيد ميلاد. مع الأخذ في الاعتبار ، تدرك أن ما تقوله هو أن العثور على "764 ، 3875 ، 4290 ، 4378 ، 764" أو شيء من هذا القبيل ليس عشوائيًا للغاية لأن الرقم في هذا التسلسل يتكرر. الطريقة الحقيقية للقيام بذلك هي مقارنة التسلسلات مع بعضها البعض. كتبت نص بيثون للقيام بذلك.

from random import randint
y = 21533456
uniques = []
for i in range(y):  
    x1 = str(randint(500, 5000))
    x2 = str(randint(500, 5000))
    x3 = str(randint(500, 5000))
    x4 = str(randint(500, 5000))
    x = (x1 + ", " + x2 + ", " + x3 + ", " + x4)
if x in uniques:
    raise Exception('We duped the sequence %d at iteration number %d' % (x, i))
else:
    raise Exception('Couldn\'t find a repeating sequence in %d iterations' % (y))
uniques.append(x)