Pajek in muha (pričakovan čas zadetka na razdaljno-regularnih grafih)

Predavanje v okviru biostatističnega centra bo v torek, 26. 10. 2021, ob 12.00 na IBMI (v kontejnerski učilnici). Predaval bo prof. dr. Aleksander Jurišić, Univerza v Ljubljani, Fakulteta za računalništvo in informatiko.

Kratek povzetek:

Predstavimo uganko s pajkovo mrežo, ki povezuje 12 vozlišč v obliki dvanajsterca. V enem vozlišču se je ujela muha, ki se ne more več premikati, v antipodnem vozlišču (tj. na maksimalni razdalji od nje) pa se nahaja slepi pajek brez spomina. Pajek se po mreži premika tako, da se v vsakem koraku naključno odloči, v katero sosednje vozlišče se bo podal (lahko tudi v tisto iz katerega je pravkar prišel). Zanima nas pričakovano število korakov, preden doseže muho (t.i. čas zadetka, angl. hitting time). Omenjenega problema se lahko lotimo z Markovskimi verigami ali pa računalniško simulacijo, a mi ga bomo rešili z metodami algebraične kombinatorike za obsežno skupino grafov (kamor spada tudi zgornji dvanajsterec) in za poljubno začetno razdaljo med pajkom in muho.