Intre matematicã şi magie

Am fãcut aluzie intr-un mesaj anterior la matematica lanţurilor Markov cu amestecare rapidã.

Dacã m-ar intreba mama mea (profesoarã de literaturã) ce inseamnã de fapt toate cuvintele astea 🙂 i-aş rãspunde cu un exemplu simplu: imaginaţi-vã un pachet de cãrţi de joc. Pornim cu un pachet complet ordonat şi le „amestecãm”. Dupã un numãr suficient de mare de amestecãri pachetul va fi aproape complet amestecat. Teoria de care v-am vorbit incearcã sã rãspundã la intrebarea: de câţi paşi e nevoie pentru asta? Nu e o problemã uşoarã.

O stare a pachetului de cãrţi la un moment dat poate fi reprezentatã de o permutare, din cele pe care le-aţi invãţat in liceu. Putem, evident, sã dãm fiecãrei cãrţi un numãr intre 1 şi 52. De exemplu, folosim ordinea valorilor

2\leq 3\leq 4\leq \ldots \leq Damã \leq Popã \leq As.

In interiorul aceleiaşi valori folosim ordonarea

Inimã roşie < Caro < Treflã < Picã

Prin urmare doiul de Treflã are valoarea asociatã 3 iar Asul de Picã are valoarea asociatã 52. O permutare e o listã ordonatã a numerelor (in cazul nostru de la 1 la 52). Câte permutãri posibile sunt ? Dacã vã amintiţi matematica de clasa a 10-a :), rãspunsul este

52! = 52\cdot 51\cdot \ldots \cdot 3\cdot 2\cdot 1

un numãr … mare :).

Imaginaţi-vã un graf cu toate stãrile posibile drept vârfuri, muchiile corespunzãnd mişcãrilor de amestecare. De exemplu, dacã folosim schema cã luãm cartea din vârful pachetului şi o punem undeva la intâmplare in pachet, atunci starea iniţialã (de fapt orice altã stare) are exact 52 de vecini (existã 52 de poziţii – inclusiv cea iniţialã – in care putem pune cartea din vârful pachetului).

Procesul de amestecare a cãrţilor il putem privi atunci drept o particulã care porneşte din starea (1,2,\ldots, 51,52) şi se mişcã la intâmplare pe acest graf. Procesul este Markovian – asta nu inseamnã decât faptul cã nu depinde de trecut: noua stare obţinutã nu depinde decât de vechea stare, şi nu de toatã istoria mişcãrilor prin care am ajuns in vechea stare.

In câţi paşi putem ajunge de la o stare la alta ? Rãspunsul depinde, evident, de metoda de amestecare folositã. Pentru metoda descrisã mai sus avem nevoie (exerciţiu !) de cel mult 52 de paşi, un numãr mult mai mic decât 52!, numãrul stãrilor. 52 de amestecãri sunt, prin urmare, in orice caz necesare (cu regula de mai sus). Nu sunt neapãrat suficienţe: ne dorim ca distribuţia obţinutã dupã t paşi sã fie foarte apropiatã de (s-ar putea sã nu fie niciodatã exact) distribuţia uniformã. S-ar putea sã fie nevoie de mai multe amestecãri.

Bun, care este pânã la urmã ordinul de mãrime al lui t ? Este el mai apropiat de 52, sau de 52 factorial ? Rãspunsul il puteţi intui: deşi in general avem nevoie de un numãr de paşi apropiat numãrului de stãri posibile ale sistemului, in acest caz concret numãrul de paşi necesar este mult mai mic: logaritmic in numãrul de stãri (cu alte cuvinte mai aproape de 52 decat de 52!). Astfel de lanţuri Markov sunt cunoscute drept lanţuri Markov cu amestecare rapidã. Teoria lor este una din realizãrile majore in informatica teoreticã a ultimilor 20 de ani. Metodele folosite sunt variate, de la tehnici combinatoriale, la variante discrete ale unor noţiuni din geometrie, la reprezentãri de grupuri şi analiza Fourier pe astfel de grupuri (despre care, poate ţineţi minte, am mai amintit).

Cititorul cu ceva inclinaţii matematice care doreşte sã ştie mai mult despre metodele folosite are la dispoziţie mai multe cãrţi (pe una din ele deja am amintit-o). Este, de asemenea, disponibil un şir de cursuri video pe tematica acestei cãrţi. Al doilea curs trateazã exact problema pe care am discutat-o, şi meritã, credeţi-mã, urmãrit.

Persi Diaconis şi matematica trucurilor magicienilor

Mã opresc aici cu ştiinţa semnalându-vã noua carte „Magical Mathematics: The Mathematical Ideas that Animate Great Magic Tricks„, scrisã de Persi Diaconis şi Ron Graham.

Persi Diaconis este probabilist, autorul cãrţii mai sus menţionate despre reprezentãrile de grupuri in probabilitãţi şi statisticã, şi in acelaşi timp magician „cu acte in regulã”, membru al asociaţiei profesionale a magicienilor din America :). Despre noua carte nu vã pot spune multe, n-am vãzut decât primul capitol (la care aveţi şi voi acces). Dar, cunoscându-l pe autor şi judecând dupâ aceastã introducere, promite sã fie o aventurã intelectualã extraordinarã …

Pentru moment vã recomand un scurt videoclip cu Persi, courtesy of The Chronicle of Higher Education, autorii unui profil extins al sãu.

Anunțuri
Acest articol a fost publicat în pop culture, popularizarea_ştiinţei. Pune un semn de carte cu legătura permanentă.

Lasă un răspuns

Completează mai jos detaliile tale sau dă clic pe un icon pentru a te autentifica:

Logo WordPress.com

Comentezi folosind contul tău WordPress.com. Dezautentificare / Schimbă )

Poză Twitter

Comentezi folosind contul tău Twitter. Dezautentificare / Schimbă )

Fotografie Facebook

Comentezi folosind contul tău Facebook. Dezautentificare / Schimbă )

Fotografie Google+

Comentezi folosind contul tău Google+. Dezautentificare / Schimbă )

Conectare la %s