Q | ciència

desembre 24, 2011

Probabilitats i l’amic invisible: quantes vegades hem de repetir l’assignació?

Abans d’ahir a la feina parlàvem sobre l’amic invisible i la probabilitat que al fer les assignacions a ningú li toqui fer-se un regal a si mateix. És a dir, si un conjunt de persones escriuen el seu nom en un paper, els barregen i en reparteixen aleatòriament un a cada un, quina és la probabilitat que ningú s’hagi quedat amb el paper que té escrit el seu nom?

Resulta que aquesta probabilitat no és res més que la proporció del número de desarranjaments (o derangements, en anglès) respecte el número total de permutacions possibles. Un desarranjament d’un conjunt $S$ és una permutació dels elements d’aquest conjunt en la qual cap dels elements no apareix en la seva posició original. O el que és el mateix, una bijecció $f:S\to S$ sense punts fixos, on $f(x)\neq x$ per qualsevol $x\in S$ .

El número de permutacions possibles d’un conjunt de $n$ elements és el factorial de $n$ : podem escollir el primer element d’entre $n$ elements diferents, el segon d’entre $n-1$ , etc., de manera que el total de combinacions possibles és $n!=n(n-1)(n-2)\ldots 1$ .

Comptar el número de desarranjaments és un xic més complex. Una manera de fer-ho és utilitzar el principi d’inclusió-exclusió. Però com en moltes altres situacions en què hem de “comptar coses”, una bona manera de fer-ho és amb funcions generatrius. Una funció generatriu és “un estenedor on pengem una seqüència de números per mostrar”, o més formalment un sèrie formal de potències, on els coeficients codifiquen la informació d’una seqüència de números $\{d_n\}$ .

Per comptar el número de desarranjaments amb funcions generatrius primer necessitem una relació de recurrència. Considerem que tenim un conjunt de $n+1$ elements, $S_{n+1}=\{1,2,\ldots,n+1\}$ . Aquest conjunt té $d_{n+1}$ desarranjaments. Agafem el desarranjament $\sigma=\{\sigma_1\sigma_2\ldots\sigma_{n+1}\}$ tal que $\sigma_{n+1}=j$ , on $1\leq j\leq n$ . Tenim dos casos possibles:

Si $\sigma_j\neq n+1$ , cada un dels elements $\sigma_i$ , amb $1\leq i\leq n$ , té un element prohibit del conjunt $\{1,2,\ldots,n\}$ (tots tenen prohibit el seu índex), i per tant en aquest cas hi ha $d_n$ desarranjaments possibles.
Si en canvi $\sigma_j=n+1$ , cada un dels $n-1$ elements $\sigma_i$ , amb $i\neq j,n+1$ té un element prohibit del conjunt $\{1,2,\ldots,j-1,j+1,\ldots,n\}$ , i per tant en aquest cas hi ha $d_{n-1}$ desarranjaments possibles.

Finalment, com que hi ha $n$ maneres diferents d’escollir $j$ , podem escriure

$\displaystyle d_{n+1} = n (d_n + d_{n-1})$

per $n\ge3$ . Si $n=1$ , no hi ha cap desarranjament possible ( $d_1=0$ ); si $n=2$ , n’hi ha un ( $d_2=1$ ). Podem definir també $d_0=1$ i així la relació anterior és vàlida també per $n=2$ . Ja tenim doncs la funció de recurrència. Ara utilitzem la funció generatriu exponencial de $d_n$ :

$\displaystyle D(x) = \sum_{n\ge0}\frac{d_n}{n!}x^n$ .

Fixeu-vos que cada terme de la sèrie és la divisió entre el número de desarranjaments i el número de permutacions per un conjunt de mida $n$ , que és just la probabilitat que estem buscant. Multipliquem per $x^n/n!$ a banda i banda de la relació de recurrència, i sumem per $n\ge0$ :

$\displaystyle \sum_{n\ge0}\frac{d_{n+1}}{n!}x^n = \sum_{n\ge0}\frac{n d_n}{n!}x^n + \sum_{n\ge0}\frac{nd_{n-1}}{n!}x^n$ .

El terme de l’esquerra és la derivada de $D(x)$ respecte $x$ . El primer terme de la dreta és $xD^\prime(x)$ , i el segon és directament $xD(x)$ . Per tant, ho podem reescriure com

$\displaystyle D^\prime(x) = xD^\prime(x)+xD(x)$ .

I d’aquí, trobar una expressió tancada per $D(x)$ fent alguna integral (i utilitzant que $D(0)=1$ ):

$\displaystyle \frac{D^\prime(x)}{D(x)} = \frac{x}{1-x}$

$\displaystyle \ln D(x) = \int \frac{x}{1-x}dx = -\ln (1-x) -x$

$\displaystyle D(x) = \frac{e^{-x}}{1-x}$

El terme $n$ -èssim de la sèrie $D(x)$ , que escrivim com $[x^n]D(x)$ , és $d_n/n!$ . Això, com hem vist abans, és la probabilitat que estem buscant: el número de desarranjaments entre el número de permutacions. D’altra banda, $[x^n]e^{-x}=(-1)^n/n!$ , i per tant la probabilitat que busquem és

$\displaystyle \frac{d_n}{n!} = [x^n]\frac{e^{-x}}{1-x} = \sum_{j=0}^n \frac{(-1)^j}{j!}$ .

A $d_n$ també se l’anomena el subfactorial, que s’escriu com $!n$ . Finalment, una última curiositat: si la mida del conjunt, $n$ , tendeix a infinit, el número de desarranjaments entre el número de permutacions (i per tant la probabilitat que el repartiment en l’amic invisible sigui vàlid) tendeix a l’invers del número $e$ :

$\displaystyle \lim_{n\to\infty} \frac{!n}{n!} = \frac{1}{e} \simeq 0.3679$ .

Per tant, és d’esperar que hàgim de repetir 3 vegades les assignacions en l’amic invisible per a que ningú es tingui a ell mateix. Però això és independent de com de gran sigui el grup que hi participa!

El problema de trobar el número de desarranjaments d’un conjunt de $n$ elements va ser plantejat per primer vegada per Pierre de Montmort el 1708, i solucionat per ell mateix el 1713 i independentment per Nicolaus Bernoulli més o menys a la vegada.

Publicat en ciència i divulgació | Deixa un Comentari »

Etiquetes: amic invisible, ciència, combinatòria, derangement, desarranjament, funció generatriu, matemàtiques, Nicolaus Bernoulli, permutació, Pierre de Montmort

setembre 11, 2011

Ciència oberta: Michael Nielsen a Barcelona

Crec que el títol ja ho diu tot. Aquest dimecres, Michael Nielsen farà una conferència a l’Institut d’Estudis Catalans sobre ciència oberta (un terme segurament més conegut en anglès, open science). Abans de promoure la ciència oberta, Michael Nielsen va ser investigador en informació quàntica, i és coautor del llibre Quantum Computation and Quantum Information, que serveix de referència en aquest camp.

La conferència serà dimecres 14 de setembre a les 19:00, a la sala Prat de la Riba de l’Institut d’Estudis Catalans (c. del Carme 47, Barcelona).

Internet està provocant un canvi radical en la manera com es produeixen els descobriments científics. A aquesta conferència explico que les col·laboracions online en massa s’estan fent servir per demostrar teoremes matemàtics i per externalitzar problemes científics. També que compartir projectes científics a la xarxa està fent possible que els aficionats duguin a terme descobriments científics. Emprar els recursos online permet amplificar la nostra intel·ligència col·lectiva i ampliar la nostra capacitat de resoldre problemes científics. Avui dia encara hi ha moltes barreres culturals que cohibeixen els científics a l’hora de fer servir els recursos online a fons. A la conferència es parlarà d’aquestes barreres, i també de la manera de superar-les.

Publicat en ciència i divulgació, in giro | Deixa un Comentari »

Etiquetes: ciència, ciència oberta, conferència, IEC, Institut d'Estudis Catalans, Michael Nielsen, open science

juny 12, 2011

Introducció a la computació quàntica

Michael Nielsen, autor del llibre Quantum computation and quantum information, ha fet uns vídeos (en anglès) que serveixen d’introducció a la computació quàntica:

The videos are short, from 5-15 minutes, and each video focuses on explaining one main concept from quantum mechanics or quantum computing.

Aquest és el primer d’ells, els altres els pots trobar aquí.

Publicat en ciència i divulgació | Deixa un Comentari »

Etiquetes: ciència, computació quàntica, física, informació quàntica, Michael Nielsen, vídeo

juny 11, 2011

El conductor distret

El problema del conductor distret, en anglès conegut com a absent-minded driver, serveix per a il·lustrar els avantatges que poden oferir les estratègies probabilístiques (o aleatòries, o mescla) en comparació amb les deterministes (o pures). Va ser proposat inicialment per Piccione i Rubinstein (1997), i posteriorment tractat per Aumann, Hart i Perry (1997). Aquí segueixo aquest segon article. També se n’ha fet una versió quàntica (Cabello i Calsamiglia, 2005), que no tractaré aquí.

El problema és el següent:

Un conductor despistat comença conduint a l’INICI de la figura. A la intersecció X pot o bé SORTIR i arribar a A (obtenint una recompensa de 0), o bé CONTINUAR cap a la intersecció Y. A la intersecció Y el conductor pot o bé SORTIR i arribar a B (obtenint una recompensa de 4), o bé CONTINUAR cap a C (obtenint una recompensa de 1). L’assumpció principal consisteix en què el conductor no pot distingir entre les interseccions X i Y, ni tampoc pot recordar si ja n’ha passat alguna d’elles.

Quina és l’estratègia que dóna una recompensa esperada més alta?

Comencem mirant les possibles estratègies deterministes. Com que les interseccions són indistingibles i el conductor no recorda si ja n’ha passat alguna, només hi ha dues estratègies possibles: o bé escollir sempre CONTINUAR (recompensa 1), o bé sempre SORTIR (recompensa 0). En aquest cas, doncs, la millor estratègia és CONTINUAR sempre.

Les estratègies probabilístiques consisteixen en decidir a cada intersecció si CONTINUAR amb probabilitat $p$ o SORTIR amb probabilitat $1-p$ . La recompensa esperada d’aquestes estratègies és

$4\cdot p(1-p)+1\cdot p^2$ .

Per $p>1/3$ , la recompensa esperada ja és més alta que en la millor estratègia determinista. I l’estratègia òptima, CONTINUAR amb probabilitat $p =2/3$ , dóna una recompensa de $4/3$ .

És a dir, confiar en l’atzar optimitza la recompensa esperada.

Referències

Michele Piccione i Ariel Rubinstein (1997): “On the Interpretation of Decision Problems with Imperfect Recall“, Games and Economic Behavior 20, p. 3-24.

Robert J. Aumann, Sergiu Hart i Motty Perry (1997): “The absent-minded driver“, Games and Economic Behavior 20, p. 102-116.

Adán Cabello i John Calsamiglia (2005): “Quantum entanglement, indistinguishability, and the absent-minded driver’s problem“, Physics Letters A 336, p. 441-447. Eprint: arXiv:quant-ph/0502136v1.

Publicat en ciència i divulgació | 1 comentari »

Etiquetes: absent-minded driver, aleatorietat, atzar, ciència, conductor distret, determinisme, matemàtiques, paradoxa, probabilitat

maig 4, 2011

Accés obert a Physical Review

Avui he rebut un correu que començava així:

Physical Review X (PRX), a new, high quality APS journal, is now accepting submissions. It features:

Broad scope covering original research in all areas of pure, applied, and interdisciplinary physics.

High APS editorial standards, and an efficient review process.

Flexible article lengths.

High visibility, rapid publication after acceptance and enhanced online content delivery.

Scientific oversight by a distinguished, international, and topically broad Editorial Board.

Global free access to all content supported by a $1500 article-processing charge to authors or their institutions.

Presenta una nova revista del grup Physical Review, publicat per l’American Physical Society, anomenada Physical Review X i que serà totalment d’accés obert. Molt bona notícia… però l’autor haurà de pagar 1.500$ per publicar l’article. Hi ha alternatives, però. Per exemple, les revistes de la Public Library of Science.

Publicat en ciència i divulgació | Deixa un Comentari »

Etiquetes: American Physical Society, APS, ciència, open access, Physical Review, Physical Review X, plos, PRX

Q

Categories

Col·leccions

Arxiu

Enviaments etiquetats ‘ciència’

Probabilitats i l’amic invisible: quantes vegades hem de repetir l’assignació?

Ciència oberta: Michael Nielsen a Barcelona

Introducció a la computació quàntica

El conductor distret

Accés obert a Physical Review

Aquest blog

Alguns enllaços

Feeds

Subscripció per email

Entrades recents

Al twitter

Etiquetes

Follow “Q”

Q

Categories

Col·leccions

Arxiu

Enviaments etiquetats ‘ciència’

Probabilitats i l’amic invisible: quantes vegades hem de repetir l’assignació?

Like this:

Ciència oberta: Michael Nielsen a Barcelona

Like this:

Introducció a la computació quàntica

Like this:

El conductor distret

Like this:

Accés obert a Physical Review

Like this:

Aquest blog

Alguns enllaços

Feeds

Subscripció per email

Entrades recents

Al twitter

Etiquetes

Follow “Q”