صفحه 1 از 2

ولگرد مست...

ارسال شده: یک‌شنبه ۱۳۸۸/۱/۳۰ - ۱۷:۳۳
توسط پين
به بهانه معرفي مساله ولگشت ( Random walk ) توسط خروش عزيز در تاپيك:
http://hupaa.com/forum/viewtopic.php?f=16&t=18701
///////////////////////////////////////////////////////////////////////
مدتي بود به دنبال بهانه اي براي شروع اين بحث بودم
اما از طرفي احتمال ميدادم كه زمان كافي براي بررسي
گام به گام آن به دستم نيايد و بحث ناقص بماند ،
هرچند همچنان نيز همين بيم را دارم اما اميد دارم كه با
ياري دوستان علاقه مند و استادان مطلعي همانند استاد
خروش عزيز ، بتوانيم اين بحث را نم نم به پيش برانيم .
بنده در نظر داشتم كه بحث را با نحوه يافتن جمله عمومي
دنباله ها شروع و با معادلات تفاضلي و تابع مولد و ...
دنبال نمايم اما اگر ديگر صاحب نظران يا استاد خروش روند
ديگري را مد نظر دارند ، بفرمايند تا چنان كنيم

خلاصه كلام اينكه در اين تاپيك ، اين ولگرد مست ، بدون
همراهي دوستان به جايي نخواد رسيد...
smile072

-پين-

///////////////////////////////////////////////////////////////////////
ساقیا باده یکی کن ، چند باشد عربده
دوستان ز اقرار مست و دشمنان ز انکار مست
شمس تبریزی به دورت هیچکس هشیار نیست
کافر و مومن خراب و زاهد و خمار مست
(ديوان شمس)

ولگشت يك بعدي :

ولگردي در هر گام با احتمال p به سمت جلو و با احتمال q=1-p به سمت عقب ميرود كه p,q ميتوانند ثابت و يا تابع مكان ( x ) باشند .
احتمال آنكه اين ولگرد در گام nام در مكان s باشد چقدر است ؟

ولگشت دو بعدي :

ولگردي در هر گام (به سمت جلو ) ، با احتمال p به سمت راست و با احتمال q=1-p به سمت چپ متمايل ميشود كه p,q ميتوانند ثابت و يا تابع مكان ( x ) باشند . احتمال آنكه اين ولگرد در گام nام در مكان s باشد چقدر است ؟
تصویر
و به همين ترتيب ،ولگشت سه بعدي...

در اين ميان ، اگر P=Q=50% در نظر گرفته شود ،آن را ولگشت متقارن ميگوييم ،


به نظرم براي شروع ، ابتدا ميتوان بحث را با اين پرسش ساده پي گرفت:

================================================================================
مستي از ميخانه خارج شده و اكنون در فاصله 74 قدمي از ميخانه است . او در هر مرحله (قدم) با احتمال 50% به جلو و با احتمال 50% به عقب ميرود ، احتمال آنكه پس از طي 4321 قدم دوباره به ميخانه بازگردد چقدر است؟

------------------------------------------------------------------------------------------------------------------------------------------------
smile072

Re: ولگرد مست...

ارسال شده: یک‌شنبه ۱۳۸۸/۱/۳۰ - ۱۷:۴۶
توسط خروش
درود و آفرين به پين، استاد بی همتا،
تاپيكی است بسيار زيبا، دست مريزاد
پيروز و شاد باشيد
smile072 smile072

Re: ولگرد مست...

ارسال شده: دوشنبه ۱۳۸۸/۱/۳۱ - ۰۰:۵۶
توسط asmann
با سلام خدمت پين و خروش گرامي smile072
پين نوشته شده:به نظرم براي شروع ، ابتدا ميتوان بحث را با اين پرسش ساده پي گرفت:

================================================================================
مستي از ميخانه خارج شده و اكنون در فاصله 74 قدمي از ميخانه است . او در هر مرحله (قدم) با احتمال 50% به جلو و با احتمال 50% به عقب ميرود ، احتمال آنكه پس از طي 4321 قدم دوباره به ميخانه بازگردد چقدر است؟
من فكر مي كنم چنين حالتي غير ممكن است، چون لازمه اش اينست كه 2197.5 قدم رو به عقب و 2123.5 قدم رو به جلو برداشته شود و گويا برداشتن نيم قدم مجاز نيست.

Re: ولگرد مست...

ارسال شده: دوشنبه ۱۳۸۸/۱/۳۱ - ۰۱:۲۲
توسط پين
درود آسمان عزيز smile072

همانطور كه متوجه شديد، احتمال خواسته شده برابر صفر است
و بنده اين مثال را سرآغاز بحث قرار دادم تا چارچوب اصلي كار مشخص شود ،
اگر فاصله مست تا ميخانه را با s و تعداد قدمها را با n نمايش دهيم ، داريم:

1) اگر s زوج باشد ، آنگاه مقدار n برابر n+2k و زوج است ، پس : s+n=زوج

2) اگر s فرد باشد ، آنگاه مقدار n برابر n+2k و فرد است ، پس : s+n=زوج

پس مي بينيم كه اگر n+s فرد باشد ، آنگاه مقدار احتمال مذكور برابر با صفر خواهد
بود( در اين مثال نيز ، s=74 و n=4321 و در نتيجه n+s مقداري فرد بود )

بنابراين در ادامه اين تاپيك ، بحث محدود به يافتن احتمال مذكور در حالتي است
كه داشته باشيم : n+s=زوج

....

Re: ولگرد مست...

ارسال شده: دوشنبه ۱۳۸۸/۱/۳۱ - ۰۱:۲۲
توسط asmann
فكر ميكنم بد نباشد براي مرحله دوم اين حالت را بررسي كنيم:
مستي از ميخانه خارج شده است. او در هر مرحله (قدم) با احتمال 50% به جلو و با احتمال 50% به عقب ميرود ، احتمال آنكه پس از طي n قدم در مكان اولش باشد چقدر است؟
در اين حالت فضاي نمونه هم شانس است.
اگر n فرد باشد، احتمال صفر خواهد بود.
اگر n زوج باشد، براي آن منظور بايد n/2 قدم به سوي جلو و n/2 قدم به سوي عقب برداشته شود، پس:
تصویر
نكته جالب اينكه اگر n به سمت بينهايت ميل كند، احتمال چنان چيزي به سمت صفر ميرود.
آيا اين تحليل درست است؟
متشكرم

Re: ولگرد مست...

ارسال شده: دوشنبه ۱۳۸۸/۱/۳۱ - ۰۱:۵۷
توسط asmann
كمي كلي تر:
مستي از ميخانه خارج شده است. او در هر مرحله (قدم) با احتمال 50% به جلو و با احتمال 50% به عقب ميرود ، احتمال آنكه پس از طي n قدم در مكان s باشد چقدر است، با فرض اينكه n+s = زوج
براي اين منظور بايد n/2 + s/2 قدم در جهت s و n/2 - s/2 قدم در خلاف جهت s برداشته شود، پس با توجه به اينكه فضاي نمونه همشانس است:
تصویر

Re: ولگرد مست...

ارسال شده: دوشنبه ۱۳۸۸/۱/۳۱ - ۱۴:۳۰
توسط mzeddot
ممنون لطفا ادامه بدین smile072

Re: ولگرد مست...

ارسال شده: دوشنبه ۱۳۸۸/۱/۳۱ - ۱۹:۳۷
توسط asmann
مستي از ميخانه خارج شده است. او در هر مرحله (قدم) با احتمال p به جلو و با احتمال q=1-p به عقب ميرود ، احتمال آنكه پس از طي n قدم در مكان s باشد چقدر است، با فرض اينكه n+s = زوج
فرض مي كنيم كه مكان اوليه شخص 0 باشد، پشت منفي، جلو مثبت
براي اين منظور بايد n/2 + s/2 قدم به جلو و n/2 - s/2 قدم به عقب برداشته شود، پس:
تصویر
فعلا تا همينجا باشد ببينيم نظر جناب پين چيست و اينكه آيا تا اينجا درست بررسي شده.
smile072

Re: ولگرد مست...

ارسال شده: دوشنبه ۱۳۸۸/۱/۳۱ - ۲۰:۵۷
توسط پين
درود آسمان عزيز smile072

آفرين، عالي بود ، smile072
هرچند بنده ديشب فرصت كافي نداشتم اما
شما بحث را به زيبايي به پيش رانديد و همانطور كه انتظار
داشتم هوشياريتان بر مستي ولگرد ما غلبه كرده .

پيشتر نيز گفتم كه اين بحث مانند بستري است كه ميتوان
مطالب كاربردي فراواني را در غالب آن پيش كشيد و بحث را
هرچه بيشتر گسترد .


-----------------------------------------------------
خروش عزيز ،
شما اگر شاگرد بپذيريد ، بنده همواره در پيشتان
در جايگاه دانش آموز هستم و به اين مي بالم

Re: ولگرد مست...

ارسال شده: سه‌شنبه ۱۳۸۸/۲/۱ - ۱۱:۴۶
توسط mzeddot
asmann نوشته شده: براي اين منظور بايد n/2 + s/2 قدم به جلو و n/2 - s/2 قدم به عقب برداشته شود
smile072
سلام می شه بگین چرا؟ چرا حالت دیگه ای نه؟ مثلا n/2-s به عقب و n/2 + s به جلو نره؟ گیج شدم یکم.

Re: ولگرد مست...

ارسال شده: سه‌شنبه ۱۳۸۸/۲/۱ - ۱۹:۲۶
توسط پين
سلام می شه بگین چرا؟ چرا حالت دیگه ای نه؟ مثلا n/2-s به عقب و n/2 + s به جلو نره؟ گیج شدم یکم
فرض كنيد ، مست در مبدا قرار دارد. تعداد قدمهاي او به سمت جلو را با x و تعداد قدمهايش به سمت عقب را y ميناميم ( x,y>0 )

1) مجموعا n قدم برداشته شده است ، پس : x+y=n
2) جابجايي نهايي برابر s است ، پس : x-y=s

و از حل اين 2معادله و 2مجهول به دست مي آيد :
x=(n+s)/2 و y=(n-s)/2
====================================

در ادامه اين پرسش را از ديدگاه متفاوت ديگري نيز مورد
بررسي قرار ميدهيم...

Re: ولگرد مست...

ارسال شده: چهارشنبه ۱۳۸۸/۲/۲ - ۱۰:۱۱
توسط ghazal
سلام.
با تشکر از پین گرامی برای طرح این مسئله

شاید ذکر برخی کاربرد های فیزیکی این مسئله جذابیت آن را افزایش بخشد...
یکی از نتایج این مسئله زیبا، percolation در فیزیک و سایر علوم است.آزمایش معروفی هم در این رابطه هست:
بین دو صفحه رسانا یک توری رسانا(دو بعدی یا سه بعدی) قرار میدهند و از این چیدمان جریانی را عبور میدهند .حال هر یک از بند های توری با احتمال p بریده و یا نگه داشته میشود...سوال اینجاست که حد p که در آن ارتباط بین دو صفحه(یا به بیان بهتر ارتباط بین خوشه های همبسته)قطع میشود چیست.هم چنین در مسائل مکانیک آماری و تئوری های گذار فاز اغلب از این رهیافت برای حل مسایل استفاده میشود.اما زیباترین کاربرد آن در محاسبات کوانتمی است.جایی که ما قرار است یک سری داده را از طریق کانال های کوانتمی که اجزای آن بصورت محلی(local)"در هم گره خورده "(entangled)هستند،انتقال دهیم.
مشتاقانه بحث شما را دنبال میکنم.
موفق باشید

Re: ولگرد مست...

ارسال شده: چهارشنبه ۱۳۸۸/۲/۲ - ۱۳:۲۸
توسط mzeddot
پين نوشته شده:
سلام می شه بگین چرا؟ چرا حالت دیگه ای نه؟ مثلا n/2-s به عقب و n/2 + s به جلو نره؟ گیج شدم یکم
فرض كنيد ، مست در مبدا قرار دارد. تعداد قدمهاي او به سمت جلو را با x و تعداد قدمهايش به سمت عقب را y ميناميم ( x,y>0 )

1) مجموعا n قدم برداشته شده است ، پس : x+y=n
2) جابجايي نهايي برابر s است ، پس : x-y=s

و از حل اين 2معادله و 2مجهول به دست مي آيد :
x=(n+s)/2 و y=(n-s)/2
====================================

در ادامه اين پرسش را از ديدگاه متفاوت ديگري نيز مورد
بررسي قرار ميدهيم...
ممنون از پاسختون. ادامه دهید لطفا و اگه می شه ما رو هم تو بحث شریک کنین.

Re: ولگرد مست...

ارسال شده: چهارشنبه ۱۳۸۸/۲/۲ - ۱۳:۳۵
توسط mzeddot
از همین معادلات استفاده شد و ثابت کردین که باید n+s زوج باشد چون نیم قدم نداریم. در این که n+s باید زوج باشد هیچ ربطی به احتمال قدم ها ندارد درست است ؟
در اون سوال اولی که مطرح کردین: مستی در 74 قدمی ...
در اون جا اصلا احتمال 50 50 مهم نبود در هر صورت مست نمی توانسته در تعداد قدم های صحیحی به میخانه برسد درسته؟؟؟

Re: ولگرد مست...

ارسال شده: جمعه ۱۳۸۸/۲/۴ - ۰۹:۲۹
توسط پين
از همین معادلات استفاده شد و ثابت کردین که باید n+s زوج باشد چون نیم قدم نداریم. در این که n+s باید زوج باشد هیچ ربطی به احتمال قدم ها ندارد درست است ؟
در اون سوال اولی که مطرح کردین: مستی در 74 قدمی ...
در اون جا اصلا احتمال 50 50 مهم نبود در هر صورت مست نمی توانسته در تعداد قدم های صحیحی به میخانه برسد درسته؟؟؟
كاملا ! همينطور است smile072

پوزش ميخواهم اگر در پاسخها و شركت در بحث ، دچار تاخير هستم .
به هر صورت ، سهام اين تاپيك متعلق به همه دوستان است و اگر
بنده نبودم ،سبب خير خواهد بود كه از محضر ديگر استادان سود ببريم