احتمال هامشي لتوليد شجرة

Question

إصلاح بعض الرسم البياني المحدود $ g= (v، e) $ ، وبعض قمة الرأس $ x $ .

لنفترض أن أقوم بإنشاء شجرة فرعية عشوائية من $ G $ الحجم $ n $ ، تحتوي على $ x $ ، كما يلي:

1. دع $ t_0={x \} $ .

2. for $ 0

   أنا. دع $ b_n $ يكون مجموعة الجيران من $ t_ {n-1} $ خارج $ t_ {n-1} $ .

   الثاني. نموذج $ t_n $ بواسطة

   • عينة زوج $ (x_n، y_n) \ in e (g) \ cap \ left (v (t_ {n-{n-1}) \ times b_n \ image) $ < / span>، مع احتمال $ q_n (x_n، y_n | t_ {n-1}) $ ،
   • إضافة $ y_n $ إلى $ v (t_ {n-1}) $ ، وإضافة $ (x_n، y_n) $ إلى $ e (t_ {n-1}) $ .

3. العودة $ t_n $ .

افترض أيضا أن $ q_n (x_n، y_n | $ يمكن حسابها بسهولة لجميع $ (t_ {n-1}، x_n، y_n) $ . أنا مهتم بكفاءة وضبط حساب الاحتمال الهامشي لتوليد الشجرة $ t_n $ ، بالنظر إلى أنني بدأت تنموها في $ t_0={x \} $ ، أي

$$ ص (t_n | t_0={x \})=sum_ {x_ {1: n}، y_ {1: n}} \ prod_ {n= 1} ^ n q_n (x_n، y_n | t_ {n-1}). $

سؤالي هو في الأساس ما إذا كان يجب أن أتوقع أن أكون قادرا على إيجاد خوارزمية فعالة (I.E.ENTOMIAL) لهذا الغرض، وإذا كان الأمر كذلك، فماذا قد يكون.

بعض الأفكار:

• بسذاجة، يحتوي المبلغ على العديد من المصطلحات المتعثرة، والتي تمنع المحاولة لتقييم المبلغ مباشرة.

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

• متعلات، وأنا أعرف كيفية حساب مقدرات غير متحيزة وغير سلبية من $ p (t_n | t_0={x \}) $ ، والتي لديك خصائص مخالفة معقولة، باستخدام تقنيات من تصفية Monte Carlo / الجسيمات المتسلسلة. هذا يشير إلى أن المشكلة لا يمكن أن تكون على الأقل تقريبية بشكل جيد في فترة زمنية معقولة.

Answer 1

لا. إذا $ Q (X_N، Y_N | T_ {n-1}) $ تعسف - يمكن أن يكون هناك اعتماد تعسفي على $ t_ {n-1} $ - ثم يتطلب هذا الوقت الأسي.

النظر في شجرة $ t_n $ يحتوي على عقدة جذر واحدة، $ N-1 $ $ 2 ^ n $ subtrees of $ t_n $ ، وعلى وجه الخصوص، هناك $ 2 ^ n $ القيم المحتملة ل $ t_n $ والتي يمكن أن تحدث في التعبير

$$ \ sum_ {x، y} \ prod_ {n= 1} ^ n q_n (x_n، y_n | t_ {n-1}). $

يمكن للمرء استخدام حجة بسيطة خصم لإثبات أن تقييم هذا التعبير يتطلب الوقت الأسي. افترض أننا تقييم $ q_n (x_n، x_n | t_ {n-1}) $ عن طريق الاستعلام عن Oracle مع $ x_n ، y_n، t_ {n-1} $ . لنفترض أن هناك شجرة واحدة $ T $ لا يتم الاستفسار عن Oracle كأي $ t_ {n-1} $ . اختر كل من $ q_n (\ cdots) $ القيم لتكون إيجابية صارمة. ثم منذ $ Q_N (x_n، y_n | t) $ لم يتم الاستعلام أثناء التنفيذ، يمكننا اختيار ذلك بعد مراقبة إخراج الخوارزمية؛ ولكن عن طريق تغييرها، يمكننا اختيار قيمة تجعل خاطئ خسارات الخوارزمية خطأ (على وجه الخصوص، تعتمد قيمة التعبير على $ q_n (x_n، y_n | t) $ لكن إخراج الخوارزمية لا يعتمد على $ q_n (x_n، y_n | t) $ ، لذلك لا يمكن إخراج الخوارزمية). لقد أثبتنا ذلك، لإنتاج الإخراج الصحيح، يجب على أي خوارزمية صحيحة الاستعلام عن Oracle for All $ 2 ^ n $ subtrees المحتملين من $ t_n $ . يستغرق الأمر على الأقل $ o (1) $ الوقت للاستعلام عن Oracle.

في الختام، تثبت هذه الحجة أن أي خوارزمية صحيحة لتحسين هذا التعبير يجب أن تأخذ $ \ أوميغا (2 ^ n) $ الوقت.

لا أعرف ما إذا كان يمكن دائما القيام به في $ O (2 ^ n) $ الوقت، أو ما إذا كان $ o (n!) $ قد يكون الوقت مطلوبا.