Tag Archives: enveloppe

Enveloppe convexe de points tirés au hasard

05/04/2018 Arthur Charpentier Leave a comment

Le week-end dernier, Jean-Baptiste qui était de passage à la maison, me présentait un problème amusant de géométrie, lié à un papier mis en ligne l’an dernier, monotonicity of facet numbers of random convex hulls. Dans cet article, ils montrent que quand on tire $n$ points au hasard (dans un espace de dimension $d$ ) alors $P_n$ , le nombre moyen de face de l’enveloppe convexe est strictement croissant avec $n$ . Si on n’a pas regardé la démonstration (on avait mieux à faire), Jean-Baptiste me disait que ce problème très simple était en fait très complexe. Et bien entendu, comme ça m’a interpelé, j’ai voulu regarder plus en détails. En dimension $d=2$ , et en tirant en plus uniformément sur le carré unité (oui, j’ai fait très très simple).

Pour tirer des points au hasard, et récupérer l’enveloppe convexe, c’est assez simple, par exemple avec 15 points

library(sp)
library(geosphere)
n=15
UV=matrix(runif(2*n),n,2)
CH=chull(UV)
PLCH=UV[c(CH,CH[1]),]
plot(c(0,0,1,1),c(1,0,0,1))
polygon(PLCH,border="blue",col=rgb(0,0,1,.3))
points(UV,pch=19,cex=2,col="red")

On le voit, ici l’enveloppe convexe est un polygône de 8 côtés (ou 8 sommets). On peut alors faire un petit code pour tirer des points au hasard, construire l’enveloppe convexe, et sortir des infos (nombre de points extrémaux, surface de l’enveloppe convexe, présence ou non de certains points – sur la diagonale, etc)

simu=function(n,isplot=FALSE){
UV=matrix(runif(2*n),n,2)
CH=chull(UV)
PLCH=UV[c(CH,CH[1]),]
nb_ex=length(CH)
p_in=function(u) point.in.polygon(u,u,PLCH[,1],PLCH[,2])
pts_in=Vectorize(p_in)(seq(.5,.95,by=.05))
if(isplot==TRUE) lines(PLCH,col=rgb(0,0,1,.25))
return(list(nb=nb_ex,area=areaPolygon(PLCH),pts=pts_in))}

par exemple

plot(c(0,0,1,1),c(1,0,0,1),col="white")
for(s in 1:1000){S=simu(5,isplot=TRUE)}

(on pourrait bien entendu stocker tout plein de choses)

ou encore avec $n=$ 20 points au lieu de 5

plot(c(0,0,1,1),c(1,0,0,1),col="white")
for(s in 1:1000){S=simu(20,isplot=TRUE)}

Essayons de boucler un peu sur $n$ maintenant

Np=c(3,4,5,6,7,8,10,15,20,30,40,50,75,100,200)
VN=VA=rep(NA,15)
NN=matrix(NA,20000,15)
VPT=matrix(NA,15,10)
for(i in 1:15){
N=A=rep(NA,20000)
PT=matrix(NA,20000,10)
np=Np[i]
for(s in 1:20000){
S=simu(np,isplot=FALSE)
N[s]=S$nb
PT[s,]=S$pts
A[s]=S$area
}
NN[,i]=N
VN[i]=mean(N,na.rm=TRUE)
VA[i]=mean(A,na.rm=TRUE)
VPT[i,]=apply(PT,2,function(x) mean(x,na.rm=TRUE))
}

Cette fois on stocke tout plein de choses. On peut juste faire un boxplot du nombre des points extrémaux en fonction de la taille de l’échantillon

VV=rep(Np,each=20000)
boxplot(as.vector(NN)~as.factor(VV))

Oui, en moyenne, ça semble croitre. Plus amusant, si on regarde la moyenne en fonction de $\log(n)$

plot(Np,VN,type="l",log="x",col="blue")

on obtient… une belle droite ! Le nombre moyen de points extrémaux croit en $\log(n)$ . On peut même avoir la pente de cette droite,

&gt; lm(VN~log(Np))
Coefficients:
(Intercept) log(Np)
0.05224 2.58717717

Je laisse les plus courageux trouver du sens à ce 2.58717… Si on continue un peu, on peut regarder la probabilité que $(u,u)$ soit à l’intérieur, pour plusieurs valeurs de $u$ .

plot(Np,VPT[,10],type="l",log="x",col="blue")
lines(Np,VPT[,8])
lines(Np,VPT[,5],col="red",lwd=2)

On retrouve des fonctions croisantes, en fonction de $n$ , mais la convexité semble dépendre de l’endroit où se trouve le point $u$ . Amusant, non ?

ECO431, Maths, Microeconomics

Théorème de l’enveloppe

28/08/2009 Arthur Charpentier 1 Comment

Un tout petit complément sur l’utilité inverse, et l’exercice 2 de la PC de jeudi après midi.
Tout d’abord un petit rappel sur le théorème de l’enveloppe. Supposons que l’on cherche à maximiser une fonction (dite objectif) $f(bold x,bold r)$ qui dépend de paramètres $bold r$ , i.e. on cherche

$f^*(bold r) = max_{bold x} f(bold x,bold r),$

La fonction $f^*(bold r)$ est alors la fonction optimale pour les paramètres $bold r$ donnés. Soit $bold x^*(bold r)$ la valeur optimale en $bold x$ , fonction du paramètre $bold r$ , de telle sorte que

$f^*(bold r) = f(bold x^*(bold r), bold r)$

Le théorème de l’enveloppe nous permet de voir comment $f^*(bold r)$ varie lorsque le paramètre change, et plus particulièrement, on a

$frac{partial f^*(bold r)}{partial r_i} = frac{partial f(bold x,bold r)}{ partial r_i} Bigg|_{bold x =$

Autrement dit, la dérivée de $f^*(bold x,bold r)$ suivant $r i$ est donnée par la dérivée partielle de $f(bold x,bold r)$ suivant $r i$ , lorsqu’on l’évalue en $bold x =$ .

Notons qu’il existe aussi une version un peu plus générale qui autorise un programme d’optimisation avec contrainte.
Supposons que l’on s’intéresse à

$max_{bold x} f(bold x,bold r) ;; s.t. ;; bold g(bold x,bold r) = bold 0$

dont le Lagrangien s’écrit

$mathcal{L}(bold x,bold r) = f(bold x,bold r) - boldsymbol{lambda} cdot bold g(bold x,bold r)$

où de manière classique $boldsymbol{lambda} = (lambda_{1},dots,lambda_{n})$ est l’ensemble de multiplicateurs de Lagrange où

$bold g(bold x,bold r) = (g_{1}(bold x,bold r),dots,g_{n}(bold x,bold r))$

Le théorème de l’enveloppe permet d’écrire

$frac{partial f^*(bold r)}{partial r_i} = frac{partial mathcal{L}(bold x,bold r)}{partial r_i} Bigg|_{ bold x =$

L’autre point important de la PC était le principe de dualité dans les programme d’optimisation, que j’avais abordé ici.
Bref, tout ça permet d’introduire la notion d’utilité inverse et de demande Hicksienne. Pour reprendre calmement cette partie (en s’inspirant d’une page de wikiversité sur le sujet), le programme classique visait à chercher

$max_{mathbf{x}in Bleft(mathbf{p},y<br /> ight)}uleft(mathbf{x}<br /> ight)$

où la contrainte budgétaire s’écrit classiquement

$B=left{mathbf{x}in X|mathbf{p}mathbf{x}=sum_{i=1}^Np_ix_i le y<br /> ight}$

La solution est alors notée $mathbf{x}^mleft(mathbf{p},y<br /> ight)$ (on parle de demande Marshalienne). Je passe rapidement sur le programme d’optimisation de l’agent, mais nous avions vu que le taux marginal de substitution était égal au rapport des prix. En effet, le Lagrangien s’écrit

$mathcal{L}equiv u(mathbf{x})-lambda(mathbf{p}mathbf{x}-y)$

ce qui donne de conditions du premier ordre de la forme

$frac{partial u(mathbf{x}^m)}{partial x_i}=u'_i=lambda p_i forall i$ .

L’idée maintenant est d’injecter les fonction de demande dans la fonction d’utilité, ce qui permet d’obtenir la fonction d’utilité inverse

$v(mathbf{p},y)=u(mathbf{x}^m(mathbf{p},y))$

Une manière alternative d’étudier ce problème est de regarder le programme dual (on a supposé la fonction d’utilité convexe), i.e on cherche à trouver le panier de bien le moins cher possible nous procurant une utilité au moins égale à une utilité minimale, i.e. on cherche à résoudre

$min_{mathbf{x}|u(mathbf{x})gebar u}mathbf{p}mathbf{x}$

La solution de ce programme d’optimisation $mathbf{x}^h(mathbf{p},bar u)$ est appelée demande hicksienne. On peut alors considérer la fonction de dépense minimale,

$e(mathbf{p},bar u)=mathbf{p}mathbf{x}^h(mathbf{p},bar u)$

Le lemme de Shepard permet d’écrire

: $x^h_i(mathbf{p},bar u)=frac{partial e(mathbf{p},bar u)}{partial p_i}$

Ce résultat se montre finalement assez simplement: en effet, par construction

$e(mathbf{p},bar u)=sum_{i=1}^Np_ix_i^h(mathbf{p},bar u)$

dont un calcul de dérivée rapide permet d’écrite

$frac{partial e(mathbf{p},bar u)}{partial p_k}={color{Red}sum_{i=1}^Np_ifrac{partial x_i^h(mathbf{p},bar u)}{partial p_k}}+x_k^h(mathbf{p},bar u)$

Rappelons que la condition de premier ordre s’écrit

$u'_i=frac{p_i}{lambda}$

Comme en $u(mathbf{x})=bar u$ , nous sommes à un optimum, on en déduit

$sum_{i=1}^Nu'_ifrac{partial x_i^h(mathbf{p},bar u)}{partial p_k}=0$

et donc

$frac{1}{lambda}{color{Red}sum_{i=1}^Np_ifrac{partial x_i^h(mathbf{p},bar u)}{partial p_k}}=0$

et comme $lambda e 0$ c’est que la somme rouge est nulle. D’où le lemme dit de Shepard.
Les théorèmes de dualité permettent d’obtenir un certain nombre de résultats, parmi lesquels

$e[mathbf{p},v(mathbf{p},y)]equiv y$
$v[mathbf{p},e(mathbf{p},bar u)]equivbar u$
$x^m_i(mathbf{p},y)equiv x^h_i[mathbf{p},v(mathbf{p},y)]$
$x^h_i(mathbf{p},bar u)equiv x^m_i[mathbf{p},e(mathbf{p},bar u)]$

Enfin, en appliquant le théorème de Slutsky, on écrit

ce qui s’écrit encore

$frac{partial x_k^m}{partial p_j}=frac{partial x_k^h}{partial p_j}-frac{partial x_k^m}{partial y}{color{Red}frac{partial e}{partial p_j}}$

Bref, on retrouve ici ce qu’on avait fait en PC.
Mais si ça n’est toujours pas plus clair, il y a des notes de cours de Michael Manove, à Boston University, sur “indirect utility” et “duality“, dont les slides sont ici. Il y a également des compléments mathématiques, dont le théorème de l’enveloppe (Prop. 21.2) ou le théorème de Kuhn-Tucker (Prop.21.13), ici.
On pourra aussi trouver en ligne l’article de Lawrence Blume sur la dualité pour le dictionnaire Palgrave d’économie, ici. Larry a aussi écrit l’article sur la programmation convexe, diponible là.
Sinon je mets ici les exercices des deux prochaines PC.

Logic & Paradoxes, Maths

Hasard et uniformité, le paradoxe des enveloppes

10/03/2009 Arthur Charpentier Leave a comment

Suite au billet de ce matin sur la loi de Benford, et sur l’erreur commune consistant à assimiler hasard et uniformité, Mathieu Rosenbaum m’a rappelé un petit paradoxe que je donnais quand je faisais la formation au concours Administrateur de l’INSEE. C’est parfois appelé le paradoxe des deux enveloppes: “Deux enveloppes contiennent chacune un chèque. On sait que l’un des chèques porte un montant double de l’autre. Le candidat choisit une des enveloppes. On lui donne la possibilité d’ouvrir l’enveloppe et de regarde le chèque, puis on lui demande s’il souhaite changer d’enveloppe. Que fait-il ?“.

Essayons de raisonner…Supposons qu’il tombe sur un chèque d’un montant X en ouvrant. Il y a deux cas possibles :

une chance sur deux que l’autre enveloppe contienne un chèque deux fois plus important (donc de valeur $2X$ );
une chance sur deux que l’autre enveloppe contienne un chèque deux fois plus petit (donc de valeur $X/2$ ).

L’espérance de gain (si on oublie l’utilité et les aspects économiques du problème) si on change d’enveloppe paraît donc être $0,5 * 2X + 0,5 * X/ 2$ , soit $1,25X$ , qui est (strictement) supérieur à X. Il faudrait donc à tout coup changer d’enveloppe. Moralité, quel que soit le montant, on a toujours intérêt à changer…. “Étonnant, non ?“. Il était d’ailleurs inutile de regarder le montant… et tant qu’à faire, si la stratégie optimale est de toujours changer d’enveloppe, pourquoi ne pas l’avoir fait plus tôt… Dès qu’on veut prendre une enveloppe, il faut prendre l’autre… enfin non, l’autre, enfin,…. bref, que fait-on ?

Il y a plein d’explications de ce paradoxe, ici par exemple. Personnellement, je retiendrais celle qui est liée à ce que je racontais sur la loi de Benford… Quand on fait le calcul des probabilités, prendre 1/2 et 1/2, c’est suppose que P(2X)=P(X/2)… et ce quel que soit X… autrement dit, on prend une loi uniforme sur l’ensemble des réels positifs (ou des entiers positifs si on suppose que le chèque est un compte rond). Mais une telle mesure de probabilité n’existe pas…

[20/03/2009] Sur le paradoxe des enveloppes et plusieurs autres “phénomènes curieux en probabilités et statistiques” je renvoie vers un cours article de Michel Emery, ici.

Freakonometrics

Tag Archives: enveloppe

Enveloppe convexe de points tirés au hasard

Théorème de l’enveloppe

Hasard et uniformité, le paradoxe des enveloppes

"sendo l'intento mio scrivere cosa utile a chi la intende…"