اختيار كفاءة مجموعة فرعية عشوائية من حجم $ M $ من مجموعة من الحجم $ n $

Question

هذا هو مشاركة عبر سؤالي هنا على الرياضيات. .

لدي قائمة من $ n $ العناصر وترغب في تحديد عشوائيا $ M $ مجموعة منه بكفاءة (من حيث تعقيد الوقت). أيضا، أريد أن يتم اختيار جميع مجموعات فرعية ممكنة مع احتمال متساو. الحل الواضح هو اختيار عدد صحيح عشوائي من $ 1 دولار إلى $ n $ واختيار العنصر المقابل، ثم كرر $ M $ مرات، وليس عد الحدث الذي يختار فيه المرء وعنصر مختار بالفعل. يصبح هذا غير فعال بشكل متزايد ك $ m $ مناهج $ n $ حتى $ M> N / 2 $ من المنطقي بدلا من المنطقي اختيار $ (NM) $ --set and ارجع مجاملة.

للحصول على قيم $ m $ قريب من $ n / 2 $ ، حلا أفضل سيكون للنظر في كل من $ n $ عناصر ويقرر إما اختيار هذا العنصر أو تجاهله، في كل مرة يقوم بتحديث احتمال التقاط أو التخلص منها حسب عدد العناصر المختارة مقابل التخلص منها قبل. على وجه التحديد، ستذهب الخوارزمية على النحو التالي (بيثون):

giveacodicetagpre.

ومع ذلك، أنا قلق من أن هذا قد لا يؤدي إلى اختيار كل مجموعة فرعية مع احتمال متساو.

لدي سؤالان. أولا، هل هذه الخوارزمية اختيار مجموعات فرعية مع احتمال متساوي (إذا كان الأمر كذلك، أود إثبات أنها تفعل وإذا لم يكن الأمر كذلك، فسأحب أيضا دليلا لا). ثانيا، على نطاق أوسع وأود أن أعرف ما هي الحلول الجيدة الموجودة في هذه المشكلة. بوضوح إذا $ m << n $ ثم الطريقة الأولى أفضل من الثانية ولكن في مرحلة ما هي الطريقة الثانية (إذا كان الأمر كذلك في العمل في الواقع) أفضل من أول. علاوة على ذلك، قد يكون نهج مختلف تماما بشكل عام.

Answer 1

احتمال أن العنصر $ 1 $ ينتمي إلى $ m $ -Subset of A Span Class="حاوية الرياضيات"> $ N $ مجموعة المعاملة هي $ m / n $ . لذلك يجب أن تشمل $ 1 $ في المجموعة الفرعية الخاصة بك مع احتمال $ m / n $ .

إذا وضعت $ 1 $ في المجموعة الفرعية الخاصة بك، ثم تركت مع اختيار $ (m-1) $ -Subset من $ (n-1) $ - مجموعة المعاملة.

إذا لم تضع $ 1 $ في المجموعة الفرعية الخاصة بك، ثم تركت مع اختيار $ m $ < / span> subset من $ (n-1) $ - مجموعة المعاملة.

هذا يعني أنه يجب عليك تحديث الخوارزمية الخاصة بك قليلا، واستبدال $ m $ مع $ M- | L | $ .

الخوارزمية الناتجة مشابهة إلى حد ما أخذ عينات الخزان .

نهج ثالث، مع بعض أوجه التشابه، يولد التقليب العشوائي من $ 1، \ Ldots، n $ واختيار الأول $ M $ إدخالات.

الجانب السلبي لجميع هذه الأساليب هي أنها تعمل في الوقت المناسب $ \ theta (n) $ ، بينما مقابل $ m \ ll \ sqrt {n} $ ، تشغيل الخوارزمية الأولى الخاصة بك في (المتوقع) الوقت $ \ tilde \ theta (m) $ .

يمكننا تحسينها على $ \ theta (n) $ وقت التشغيل كما يلي. سنقوم بإنشاء عشوائي $ m $ -Subset معطى $ m $ المؤشرات $ i_1، \ Ldots، i_m $ ، حيث $ i_j \ in \ {1، \ ldots، n- (j-1) \} $ <} \} $ < / span>. $ J $ 'العنصر الفرعي سيكون هو $ i_j $ "أصغر عدد في < Span Class="حاوية الرياضيات"> $ \ {1، \ Ldots، n \} $ من الأرقام غير المختارة بالفعل.

من أجل إكمال وصف الخوارزمية، نحتاج إلى حل المشكلة التالية: معطى $ s \ subseteq \ {1، \ ldots، n \} $ و $ i $ ، ابحث عن $ I $ "أصغر عنصر في $ \ overline {s} $ . يمكننا أن نفترض أن $ S $ يتم تخزينها في هيكل (مثل شجرة ثنائية موازنة ذاتية) والتي يمكن أن تجيب بكفاءة من النوع التالي من الاستعلام: معطى $ x $ ، كم عدد العناصر في $ S $ أصغر من $ X $ . يمكننا بعد ذلك العثور على $ i $ "أصغر عدد في $ \ overline {s} $ باستخدام ثنائي البحث.

بشكل عام، تعمل هذه الخوارزمية في $ \ tilde \ theta (m) $ لجميع قيم $ m $ < / SPAN>، حيث يخفي Tilde عوامل لوغاريتمي في $ n $ . (عندما $ m \ ll \ sqrt {n} $ يمكننا استخدام نهجك الأول، وبالتالي التخلص من هذا الاعتماد على $ n $ .)