04 augusta 2009

Ondrova-Misofova rekurencia

Predchádzajúcu zaujímavú úlohu od Ondra by sme mali vyriešenú, ak by sa nám podarilo dokázať jednu celkom pozoruhodnú domnienku, ktorú v komentároch formuloval misof a ktorú je možné zapísať v nasledovnom tvare:


Nech Q1=0, Q2=1/3 a pre n=3,4,5,... nech


Potom

Numericky táto domnienka sedí natoľko presne, že jej platnosť je prakticky istá. Ide len o jej formálny dôkaz...

Ja sa do rekurencií veľmi nevyznám, ale všimol som si, že Ondrova-Misofova rekurencia spĺňa jednu peknú vlastnosť: Člen Qn je váženým priemerom členov Q1, Q2,...,Qn-2. Z toho je napríklad okamžite jasné, že všetky členy postupnosti budú medzi číslami Q1 a Q2. Je ale možné toto pozorovanie použiť na dôkaz skutočnosti, že postupnosť hodnôt Qn konverguje, prípadne dokonca toho, že konverguje práve k číslu e-2? Vyzerá to byť pekná a netriviálna matematická úloha...

6 komentárov:

Ruziklan povedal(a)...

No, samotna konvergencia by hadam mohla vyplyvat z tusim Leibnizovho kriteria (pokial by sa dal vseobecne vycislit rozdiel Q(k)-Q(k-1) a ukazalo sa, ze je to alternujuce cislo konvergujuce k nule), ale presna hodnota je dost fascinujuca. Uz sa tesim, ako sem niekto mrskne trikovy dokaz na 3 riadky :-)

ivansml povedal(a)...

Konvergenciu k e^-2 sa mi ukazat nepodarilo, po chvili hrania som ale prisiel na to, ze vztah sa da prepisat na diferencnu rovnicu druheho radu:
Q_{n} = a(n) * Q_{n-1} + b(n) * Q_{n-2}
kde
a(n) = (n-3)*n / ((n-2)*(n+1))
b(n) = 2*(n-1) / ((n-2)*(n+1))
Kedze rovnica ma nekonstantne koeficienty, nic dalsie ma nenapadlo, tak mozno niekto mudrejsi bude mat vacsi uspech :)

Nanyk povedal(a)...

trocha pocitania da

Q_n-Q_{n-1}=4(n-1)(Q_{n-2}-Q_{n-3})/{(n+1)n(n-3)}

a tak

lim Q_n = \Sum_{n=1} (-2)^{n-1}(n-1)/(n+1)!

co scitame neferovo

\Sum_{n=0} nx^n/(n+2)! v bode -2 je x(\Sum x^n/(n+2)!)'=
x(x^{-2}(e^x-x-1))'=x(-2x^{-3}(e^x-x-1)+x^{-2}(e^x-1)) v bode -2, co je -2(1/2)e^{-2}=-e^{-2} znamienko sa stratilo asi v prvej rovnosti, neviem

kuko povedal(a)...

zda sa ze nanyk ma predbehol; pozeram, ze odkedy som tu bol naposledy ste s ulohou pohli; ja som robil este s tou starou ondrovou rekurenciou; podla mna je dobra
s tym ze E_n = R_{n-2} ako pisal misof;
(n-1)E_{n+2} = (n-2)E_{n+1} + 2E_n
pricom chceme spocitat podiel P_n = E_n/n
teda E_n = nP_n a po dosadeni dostaneme
(n+2)(n-1)P_{n+2} = (n+1)(n-2)P_{n+1} +2nP_n
toto som dokazoval ze konverguje (hoci som este nevedel k comu); vsimol som si, ze sa to da napisat aj takto:
(n+2)(n-1)(P_{n+2} - P_{n+1}) = -2P_{n+1} -2P_n
ak si oznacime rozdiel D_n = P_{n+1}-P_n
dostaneme
D_{n+1} = -2n / (n+2)(n-1) * D_n
co uz je lahka rekurencia; ak ju rozvinieme dostaneme
D_{n+1} =-n * (-2)^n/(n+2)!
pricom P_n je sucet D_n
a to uz sa lahko vyrobi cez generujuce fn. a dosadenim -2 ako hovoril Nanyk...
pekna uloha...

Ondro Budac povedal(a)...

Ejha :) tak predsa... Som rad, ze ste sa s tym takto popasovali. A to pribeh s diktatormi zdaleka nekonci. Teda, toto je len zaciatok celeho badania :)

Preformulujme si trosku zadanie. Namiesto toho, aby sa nejaka nahodna dvojica planetok navzajom znicila, tak do seba naburaju a vznikne tak dvojplanetka. (Dvojplanetky sa zatial spajat nemozu). Zisili sme, ze na konci spajania sa planetok do dvojplanetok nam zostane priblizne e^{-2} planetok a (1-e^{-2})/2 dvojplanetok.

Diktatori si uvedomia, ze by mohli vzniknut aj trojplanetky a tak niektore nahodne dvojice susediacich planetok a dvojplanetok zacnu vytvrat trojplanetky. Nahodny proces pokracuje az kym opat ziadna trojplanetka nemoze vzniknut. Ake bude zastupenie planetok, dvojplanetok a trojplanetok na konci tohoto procesu?

V dalsom kroku si pockame kym sa vytvoria vsetky mozne stvorplanetky, potom patplanetky, ... a ako spravny matematici, n-planetky. Pritom si po kazdom kroku do nejakeho histogramu zakreslime ako vyzeraju stredne hodnoty zastupeni jednotlivych velkosti.

Tieto rozlozenia sa (po vhodnom preskalovani) budu na seba velmi podobat, az si jeden zaumieni, ze by mohol dokazat, ze sa blizia k nejakemu spojitemu rozdeleniu. Otazka znie, ake to rozdelenie je :)

Nas v praci az tak nezaujima, ako sa to sprava (tento model tam nakoniec vobec nerozoberame), ale niekedy zo zaciatku sme si na tomto ukazovali ako funguje "coagulation with maximal size". Koho to trosku zaujalo, mozete si kuknut tak prve dve stranky z www.lps.ens.fr/~boudaoud/Publis/Boudaoud07Aggreg.pdf

Radoslav Harman povedal(a)...

Chalani, velmi dobre! Budem sa venovat tomuto zaujimavemu problemu hned ako sa vratim z Cardiffu.