متى يحل خوارزمية مونتي كارلو مشكلة؟

Question

متى يمكننا القول أن خوارزمية مونتي كارلو يحل مشكلة؟

إلى اقتباس من wikipedia على خوارزميات مونت كارلو

على سبيل المثال، يتم استخدام اختبار البدادة الأولية Solovay-Strassen لتحديد ما إذا كان رقم معين هو رقم رئيسي.يجيب دائما صحيحا لمدخلات الأرقام الرئيسية؛للمدخلات المركبة، يجيب على FALSE مع احتمال ما لا يقل عن وصحيح مع احتمال أقل من.

ماذا سيحدث إذا كان اختبار Solovay-Strassen يجيب صحيحا مقابل 1٪ فقط من المدخلات المركبة؟

هل ما زالنا نقول أنه يحل مشكلة اختبار البدائية؟

أو هل هناك بعض المتطلبات مثل خوارزمية Monte Carlo يجب أن تجيب صحيحة لأكثر من نصف الحالات؟

Answer 1

يتم استخدام

بشكل عام Monte Carlo لحل مجموعة واسعة من أنواع مختلفة من المشاكل. في هذه الحالة بالذات، تريد أن تتعلم ما إذا كان متغير عشوائي هو ثابت 1، أم لا. الفكرة واضحة، عينة المتغير العشوائي عدة مرات، (كل عينة بشكل مستقل عن العينة السابقة لتجنب التحيز) وتحقق مما إذا كانت جميع النتائج 1. إذا كان هناك بعض النتيجة على الأقل 0، فنحن نعلم بالتأكيد المتغير العشوائي ليس كذلك ثابت 1 (في سياق اختبار Solovay-Strassen، الرقم مركب).

من المهم التأكيد، نظرا لأن Monte Carlo عبارة عن خوارزمية عشوائية، فإنه يقال إنه يحل المشكلة إذا كان احتمال إعادة الإجابة الخاطئة أقل من بعض العتبة (عدد قليل سوف نسميها $ \ Epsilon $ ).

ماذا يحدث إذا كانت جميع النتيجة 1؟ هناك فرصة لأنها ثابتة 1، ولكن أيضا هناك فرصة لم تكن محظوظا وكل النتيجة 1 عندما تكون أيضا 0. إذا كان احتمال أخذ العينات A 1 هو $ P <1 $ ، بعد $ n $ عينات احتمالية الحصول على الكل 1 هو $ p_n= p ^ n $ . لاحظ أنه في حين $ n $ زيادة $ p_n \ charnarrow 0 $ . يمكننا تحديد عتبة، دعنا نقول $ \ Epsilon= 10 ^ {- 10} $ ، بحيث إذا $ p_n < \ Epsilon $ (أي احتمال وجود إيجابي كاذب أقل من $ \ Epsilon $ ) نحن موافق مع هذه النتيجة.

---

الآن الإجابة على سؤالك. $ \ forall p <1، \ epsilon> 0 \ space \ موجودة n \ space p ^ n <\ epsilon $ . ما هذا يخبرك بالضبط؟

مهما كان احتمال النجاح، بقدر ما تكون أقل من $ 1 $ (على سبيل المثال $ p= 0.99 دولار أو $ p= 0.01 دولار أو $ p= 0.5 $ ) والعتبة $ \ Epsilon $ هناك $ n $ مثل هذا إذا قمت بتشغيل التجربة $ N $ Times (عينة $ n $ أضعاف المتغير العشوائي بشكل مستقل) سنفشل مع الاحتمال في معظم $ \ Epsilon $ . لذلك يمكن تطبيق مونتي كارلو على القيم غير المتوفة من $ p $ ، فقط الرقم $ n $ من العينة يجب تعديلها لإرضاء $ \ Epsilon $ متطلبات العتبة.