[MD-sorular] free group üzerinde basit rastgele yürüyüş

E. Mehmet Kıral luzumi at gmail.com
15 Eki 2011 Cmt 02:42:51 EEST


Geri donen rasgele yuruyusler icinde ilk kacinci hamlede tekrar baslangic
noktasina gelmesi bir "random variable" olsun. Bu rasgele degisken'in
beklentisi nedir. Yani yol geri donecekse ilk ne zaman donmesi beklenir.

 Cevabi bulamadim ama cevap 2'ye oldukca yakin, 8/3'ten kucuk olmasi
gerektigini soyle gosterebilirim.

Bir kere ozgur grupta hic iliski olmadigindan, ancak geldigimiz yolu geri
teperek basladigimiz noktaya gelebiliriz. Bu da sadece cift sayili adimlarda
baslangica gelebilecegimizi gosterir. 2n. adimda 1'e gelme olasiligimiz icin
bir hesap 1/4^n olabilir. Tabii bu olasilik daha once 1'e ugramis olma
olasiligimizi hesaba katmiyor. Yani ilk defa 2n. hamlede basa gelme
olasiligimiz daha dusuk. Bir tek 2. hamlede geri donme olasiligi 1/4 aynisi.
Bu sayiyla hesabi yaparsak,

SUM 2n/4^n = 8/9.
Bir de kendimizi geri donusu olan rasgele yollar altkumesine (olcumu 1/3
olan bir altkume) kisitladigimizdan, olcumuzu (measure) tekrar olasilik
olcusu olacak sekilde normalize edersek, beklenti
8/3'ten kucuk olur. Kucuk olacagini biliyoruz cunku buldugumuz sayi 2 ile 4
arasinda, ve 4 ve 4'ten buyuk tum degerlerin olasiligini fazla fazla
hesapladik.

Ozyinelemeli (recursive) bir bicimde ilk defa 2n. hamlede 1'e gelme
olasiligini bulabilirim, ancak bunun kapali bir yolunu bulacak ve kacinci
hamlede geri donecegimiz beklentisini hesaplayacak var mi?

2011/10/14 İrem Portakal <pirem at hotmail.com>

>
> Anladım! Teşekkürler.
>
> İrem.
>
> > Date: Sat, 15 Oct 2011 02:02:26 +0300
> > From: anesin at nesinvakfi.org
> > To: pirem at hotmail.com
>
> > Subject: Re: [MD-sorular] free group üzerinde basit rastgele yürüyüş
> >
> >
> > Evet!
> > 1'den uzaklasmak, 1'e yakinlasmak olarak dusun. Olasiliklar 3/4 ve 1/4.
> > A
> >
> > On 15.10.2011 02:01, İrem Portakal wrote:
> > >
> > > Evet, 1 olması gerekir.Ama olasılığın neden 1/3 olduğunu anlayamadım.
> Makaleye göre, p'yi 1/4 q'yu 3/4 gibi mi düşünmemiz gerekiyor?
> > >
> > >> Date: Sat, 15 Oct 2011 01:23:54 +0300
> > >> From: anesin at nesinvakfi.org
> > >> To: pirem at hotmail.com
> > >> CC: md-sorular at matematikdunyasi.org
>
> > >> Subject: Re: [MD-sorular] free group üzerinde basit rastgele yürüyüş
> > >>
> > >>
> > >> Evet, tanim boyleyse, F_2 recurrent olamaz. Ama bunu kanitlamak icin
> > >> referans verdigim makale yeter saniyorum. O makaleden su cikar: 1'den
> > >> baslayip rastgele yuruyusun bir defa daha 1'e gelme olasiligi 1/3.
> Demek
> > >> ki sonsuz defa 1'den gecme olasiligi 0.
> > >> Rastgele yurusuyusun sonsuz defa 1'den gecme olasiliginin pozitif
> olmasi
> > >> icin, 1'den baslayan bir sonsuz yuruyusun bir defa daha 1'e gelme
> > >> olasiliginin 1 olmasi gerekmez mi?
> > >> A
> > >>
> > >>
> > >> On 15.10.2011 00:53, İrem Portakal wrote:
> > >>> Evet, (F_{2}, {a^(+1,-1), b^(+1,-1)}) ile kastettiğim free grubun
> Cayley çizgesi. Yani elimizde 4-regular tree var.Recurrent olmak da şu
> şekilde tanımlanıyor: Bir basit rasgele yürüyüşe recurrent diyoruz eğer bu
> yürüyüş boyunca grubun etkisiz elemanını pozitif olasılıkla sonsuz defa
> ziyaret ederse.
> > >>> Önerdiğiniz makale işime yaradı teşekkürl er.
> > >>> Ama sanırım bir de, biraz hileyle (ve ispatlanması gereken bir sürü
> teoremle) recurrent olmadığına şöyle ulaşabiliyoruz. Çizgemiz, Liouville
> değilse recurrent değildir. Non-amenable gruplar Liouville değildir. Free
> grup non-amenable olduğundan ilgili çizge recurrent değildir (!).
> > >>>> Date: Thu, 13 Oct 2011 07:33:10 +0300
> > >>>> From: anesin at nesinvakfi.org
> > >>>> To: luzumi at gmail.com
> > >>>> CC: pirem at hotmail.com; md-sorular at matematikdunyasi.org
> > >>>> Subject: Re: [MD-sorular] free group üzerinde basit rastgele yürüyüş
> > >>>>
> > >>>> O zaman sozunu ettigim makale cozum yolunu gosterir.
> > >>>> A
> > >>>>
> > >>>> On 13.10.2011 06:52, E. Mehmet Kıral wrote:
> > >>>>> Internette recurrent rasgele yuruyusun tanimi farkli veriliyor
> ancak. Eger
> > >>&gt ;>> basladigin noktaya kesin olarak geri donuyorsan ona yinelenen
> yuruyus
>
> > >>>>> deniyor.
> > >>>>>
> > >>>>> Amac geri donme ihtimalinin 1 olmadigini gostermek oldugu icin geri
> donme
> > >>>>> olasiliginin en az 1/3 olmasi bununla celismiyor.
> > >>>>>
> > >>>>> 2011/10/12 Ali Nesin<anesin at nesinvakfi.org>
> > >>>>>
> > >>>>>> **
> > >>>>>>
> > >>>>>> Problemi dogru anliyor muyum acaba?
> > >>>>>> 1'den basliyorsun ve her adimda bir onceki elemani (diyelim)
> soldan a,
> > >>>>>> a^{-1}, b ve b^{-1} ile esit (yani 1/4) olasiliklarla carpiyorsun.
> Tekrar
> > >>>>>> 1'e gelme olasiligindan soz ediyorsak, daha ikinci adimda 1/4
> olasilikla
> > >>>>>> geri donuyorsun.
> > >>&g t;>>> Sanirim 1/3 olasilikla bir zaman sonra 1'e geri donersin.
>
> > >>>>>>
> http://www.matematikdunyasi.org/arsiv/makaleler/118_122_cekirge.pdf yazim
> > >>>>>> belki sana bir fikir verebilir.
> > >>>>>> A
> > >>>>>>
> > >>>>>>
> > >>>>>> On 13.10.2011 01:41, İrem Portakal wrote:
> > >>>>>>
> > >>>>>> Merhaba,
> > >>>>>> (F_{2}, {a^(+1,-1), b^(+1,-1)}) üzerinde basit rastgele yürüyüşün
> recurrente olmadığını gösterin.
> > >>>>>> F_{2}, iki elemanla gerilmiş free group'u temsil ediyor.Bu cevabı
> oldukça uzun olan bir soru olabilir. Düşünmeye nereden başlamalıyız diye
> fikir almak istedim.
> > >>>>>> İrem.
> > >>>>>>
> > >>>>>>
> > >>>>>>
> > > >>>>>
> > >>>>>> _______________________________________________
> > >>>>>> MD-sorular e-posta listesisorular at matematikdunyasi.orghttp://
> lists.math.bilgi.edu.tr/cgi-bin/mailman/listinfo/md-sorular
> > >>>>>>
> > >>>>>>
> > >>>>>> _______________________________________________
> > >>>>>> MD-sorular e-posta listesi
> > >>>>>> sorular at matematikdunyasi.org
> > >>>>>>
> http://lists.math.bilgi.edu.tr/cgi-bin/mailman/listinfo/md-sorular
> > >>>>>>
> > >>>
> > >
>
> _______________________________________________
> MD-sorular e-posta listesi
> sorular at matematikdunyasi.org
> http://lists.math.bilgi.edu.tr/cgi-bin/mailman/listinfo/md-sorular
>



-- 
Eren Mehmet Kıral
-------------- sonraki bölüm --------------
Bir HTML eklentisi temizlendi...
URL: <http://lists.math.bilgi.edu.tr/pipermail/md-sorular/attachments/20111014/f153581a/attachment.htm>


MD-sorular mesaj listesiyle ilgili daha fazla bilgi