Welcome to Randal Douc's wiki

You've loaded an old revision of the document! If you save it, you will create a new version with this data.

====== A first illustrative example ======

Two men are sitting in a bar.

> I am bored, man…
>> Then, write two different real numbers on two papers and close them.
> Done.
>> I will disclose only one of these papers. And I will tell you with probability strictly larger than 1/2, which paper contains the largest real number.
> You are kidding! How can you do that?

<note warning>Two different real numbers are in a basket but we don't have access to their values. Pick at random one of them in the basket with equal probabilities and see its value. The question is to find a decision process which allows you to indicate, with a probability strictly larger than $1/2$, which one is the largest . </note>

<hidden Answer> $ \newcommand{\rset}{\mathbb R} \newcommand{\PP}{\mathbb P}$ Denote by $X$ the chosen real number that you have in your hand. Let $\alpha: \rset \to (0,1)$ be a (strictly) increasing measurable function. With a probability $\alpha(X)$, say that the largest real number is the one in your hand and otherwise say that this is the one in the basket.

The proof proceeds as follows. Denote by $X_0$ (resp. $X_1$) the smallest (resp. largest) real number. Assume $X=X_0$, we give a right answer if we choose the number in the basket and this event holds with probability $1-\alpha(X_0)$. Assume now $X=X_1$, then we give a right answer if we choose the number in our hand and this holds with probability $\alpha(X_1)$. And since $\PP(X=X_0)=\PP(X=X_1)=1/2$, we finally get $$ \PP(\mbox{right answer})= \frac12 (1-\alpha(X_0))+\frac12 \alpha(X_1)=\frac12+ \underbrace{\frac{\alpha(X_1)-\alpha(X_0)}{2}}_{>0} >\frac12 $$ </hidden>

<hidden Answer> As before, denote by $X$ the chosen real number that you have in your hand.Let $\mu$ be a probability measure on $\mathcal B(\rset)$ such that $\mu([a,b])>0$ for any $a,b \in \rset$, $a\neq b$. Pick a random number $Y$, simulated according to the measure $\mu$. Then the strategy is the following: if $X<Y$, you bet that the remaining number in the hat is the largest, and if $X>Y$, you bet that the number in your hand is the largest. Said otherwise, since you don't know what other number is in the basket, you just simulate one that will play his role! (and you do so with the distribution of your choice...) We get here $$ \PP(\mbox{right answer})=\frac12+\frac12 \mu([X_0, X_1]) > \frac12$$ The strategy given in the first answer is the same as this one, if you take the function $\alpha$ to be a (strictly increasing) cumulative distribution function. If the guy chosing the numbers in the hat knows about this strategy, he will choose the numbers $X_0$ and $X_1$ very close to each other, so that he can make your probability of guessing right as close as he wants to $\frac12$. </hidden>

====== A more general example ======

A man has three thousand euros for buying a car. He hesitates between two cars. He bought one of them with probability 1/2. One year later, his friend also wants to buy one of these two cars. He wants to take profit of the experience of his friend and asks his friend how many failures he had with his car. Modelling the number of failures with a Poisson distribution, could you help the friend for getting a new car?

More generally, the framework can be a joint distribution on $(X_0,X_1)$, and we focus on $(X_0 \wedge X_1,X_0 \vee X_1)$. Actually since the distributions of these two variables are stochastically dominated, the problem can be some kind of two-armed bandit problem where each arm delivers a random variable. If the two distributions are stochastically ordered, then the aim is to find the arm which corresponds to the distributiion which dominates the other one. The optimal function $\alpha$ corresponds to the cumulative function associated to probability measure which put most of its mass on the $x$ where $\PP(X_0 \vee X_1 \leq x)-\PP(X_0 \wedge X_1 \leq x)$ is maximal.

Please fill all the letters into the box to prove you're human. M Q P G P Please keep this field empty:

Edit summary

Welcome to Randal Douc's wiki

User Tools

Site Tools

Page Tools