متوسط ​​التوزيع مع قيود الذاكرة

Question

مهمة

أريد أن تقريب متوسط ​​توزيع معين $د$ التي يمكنني أخذ عينة منها.

خوارزمية بسيطة لهذا، وذلك باستخدام $ن$ العينات، هي:

samples = [D.sample() for i in range(n)] # generate n samples from D
sort(samples)
return samples[n/2]

ومع ذلك، أنا أبحث عن خوارزمية ذلك يتطلب أقل من $O(ن)$ فضاء.

أفكار

لقد بحثت في هذه الخوارزميات:

• وسط المتوسطات:الاحتياجات $O(ن)$ الفضاء، لذلك لا يعمل بالنسبة لي.
• متوسط ​​​​العشوائية:يبدو أن هذا يمكن تعميمه بسهولة على الخوارزمية التي تستخدم $O(ن^{3/4})$ فضاء.

هل هناك أي خوارزميات أخرى تستخدم أقل من ذلك الحين $O(ن)$ المساحة التي يمكن أن تحل مشكلتي؟على وجه الخصوص، كنت أفكر أنه قد يكون هناك خوارزمية تستخدم $O(م)$ الفضاء عن طريق توليد دفعات من العينات من $د$ من الحجم $م$...

تفاصيل

• من الناحية المثالية، أنا أبحث عن مرجع لخوارزمية تتضمن أيضًا التحليل (احتمالية النجاح، وقت التشغيل المتوقع، وما إلى ذلك).
• في الواقع، أنا بحاجة إلى خوارزمية لتقدير $د$'س $p$-المئوي ل معين $p$, ، لكنني آمل أن يتم تعميم معظم خوارزميات إيجاد الوسيط على ذلك.
• أرغب في تحقيق نفس الدقة مثل الخوارزمية البسيطة الموضحة أعلاه.إحدى طرق تحقيق ذلك هي استخدام خوارزمية يكون توزيع مخرجاتها هو نفس خوارزمية العينة (ولكن ربما تفشل الخوارزمية الجديدة في حالات نادرة)

Answer 1

بالتأكيد، يمكنك بالتأكيد تحقيق ذلك باستخدام وقت تشغيل أطول قليلاً.فيما يلي طريقة بسيطة من الناحية النظرية، والتي قد لا تكون الأمثل، ولكنها ستساعدك على البدء وربما تكون جيدة جدًا:

استخدم البحث الثنائي للعثور على متوسط ​​تقريبي $م$.كيف يمكنك معرفة ما إذا كان المرشح $م$ هل هو كبير جدًا أم صغير جدًا؟عينة $ن'$ مرات من التوزيع، وحساب عدد مرات العينات $\ge م$, ، وقارن هذا العدد بـ $ن'/2$.يمكن القيام بذلك مع $O(1)$ فضاء.

ثم يصبح السؤال الرئيسي:كيف نختار $ن'$, للتحكم في احتمالية الخطأ؟النهج البسيط هو الاختيار $ن'$ أن تكون أكبر بما فيه الكفاية من $ن$ أن احتمال الخطأ في كل تكرار للبحث الثنائي هو $t$ أصغر من احتمال الخطأ عند الاستخدام $ن$ العينات، حيث $t$ هو عدد تكرارات البحث الثنائي اللازمة لتحقيق الدقة المطلوبة.بعد ذلك، يضمن الارتباط النقابي أن هذا سوف يلبي شروط الدقة الخاصة بك.

لسوء الحظ، من الصعب بعض الشيء التعامل مع شرط الدقة الخاص بك، عندما لا نعرف أي شيء عن توزيع البيانات، حيث يمكن أن تكون دقة متوسط ​​العينة سيئة بشكل تعسفي.على سبيل المثال، النظر في التوزيع الذي يخرج $0$ مع الاحتمال $(1-\ إبسيلون)/2$ و $100$ مع الاحتمال $(1+\إبسيلون)/2$. $\gg 1/\إبسيلون^2$ عينات).وهذا توزيع سيئ للغاية، وسيكون من الصعب العمل معه.ولكن إذا افترضت أن التوزيع تقريبًا غاوسي (على سبيل المثال) مع الانحراف المعياري $\سيجما$, ، ثم خطأ متوسط ​​العينة، مع $ن$ العينات، تقريبا $1.25 \سيجما/\sqrt{n}$.وبالتالي، يمكن استخدام الخوارزمية المذكورة أعلاه في المكان الذي حددناه $t \approx \lg (\sqrt{n}/1.25)$ ووضعنا $n' \تقريبًا n t^2$.

هذا نهج واحد بسيط.ربما يمكنك أن تفعل ما هو أفضل.قد ترغب في البحث عن خوارزميات التدفق لحساب الوسيط، لأنها تعالج المشكلة التي تتعامل معها:بالنظر إلى عدد غير محدود من العينات من التوزيع، ولكن مساحة محدودة فقط، ما هو أفضل تقدير يمكننا الحصول عليه للوسيط؟على سبيل المثال، إليك خوارزمية واحدة بسيطة:تأخذ الطبقة الأولى ثلاث عينات بشكل متكرر وتخرج متوسط ​​تلك العينات الثلاثة؛تأخذ الطبقة الثانية بشكل متكرر ثلاثة أرقام من الطبقة الأولى وتخرج متوسط ​​تلك الأرقام الثلاثة؛وما إلى ذلك وهلم جرا.بعد عدد الطبقات اللوغاريتمي، تحصل على تقدير تقريبي معقول للوسيط.هناك أدبيات كاملة حول هذا الموضوع، ويجب أن تكون قادرًا على العثور على المزيد.