Predict if this is the larger number with a probability greater than half?

Probability Level 4

Alice and Bob are playing a game.

Alice has two slips of paper, on each of which she has written down a distinct real number. Bob reads one slip at random with the other slip hidden from him.

Bob then needs to decide if the number he read is the larger of the two. In the best strategy, what is his probability of getting it correct?

A half 0 A number strictly greater than a half but smaller than 1 1 A positive number strictly less than a half

1 solution

Kenny Lau
Feb 21, 2017

Pick any probability density function $f$ that is strictly positive anywhere. That is:

$\displaystyle f: \Bbb R \to (0..\infty)$
$\displaystyle \int_\Bbb R f \left({x}\right) \ \mathrm dx = 1$

Choose a number from $\Bbb R$ according to $f$ and name it $x$ . Denote the number that Bob read as $y$ .

If $x < y$ , decide that $y$ is the larger . If $x > y$ , decide that $y$ is the smaller. The case $x=y$ occurs with a probability zero and can be discarded.

Reference: Pick the largest number, Thomas M. Cover

Proof:

Denote the two numbers that Alice wrote as $a$ and $b$ , with $a < b$ .

	$y = a$	$y = b$
$x < a$	✗	✓
$a < x < b$	✓	✓
$b < x$	✓	✗

Note that the left column and the right column occur with an equal probability, namely a half.

Therefore, the probability:

$= \displaystyle \frac 1 2 \int_{-\infty}^a f \left({x}\right) \ \mathrm dx + \int_a^b f \left({x}\right) \ \mathrm dx + \frac 1 2 \int_b^\infty f \left({x}\right) \ \mathrm dx$

$= \displaystyle \frac 1 2 + \frac 1 2 \int_a^b f \left({x}\right) \ \mathrm dx$

$> \displaystyle \frac 1 2$

This actually leads to an interesting philosophical question. Can Bob choose a random number with a [strictly increasing] continuous distribution?

Obviously, if he can, then this strategy applies, but in practice we can only approximate continuous random numbers with discrete random variables.

Brian Moehring - 4 years, 3 months ago

Since the cumulative density function is continuous and you're comparing against a number, yes you can. Roll a 10-sided die numbered 0-9 over and over. You're constructing a decimal number in the form $0.d_1 d_2 d_3 \ldots$ where $d_1, d_2, d_3, \ldots$ are your rolls in order. But you don't need to roll infinitely many times! Suppose you've rolled $n$ times, getting the number $p = 0.d_1 d_2 d_3 \ldots d_n$ . Now, since the cumulative density function $f$ is continuous, there exists $a, b \in [-\infty, \infty]$ such that $f(a) = p, f(b) = p + 10^{-n}$ . (Intermediate value theorem, and noting that $p \le 1 - 10^{-n}$ . If $p = 0$ , take $a = -\infty$ ; if $p = 1 - 10^{-n}$ , take $b = -\infty$ .)

The trick is that if $y$ is outside the range $[a,b]$ , then we're already sure where our generated number will fall to. The number $x$ that the solution above uses must be inside the range $[a,b]$ , since we know $p \le f^{-1}(x) \le p+10^{-n}$ . Thus if $y < a$ , then we know whatever $x$ will be, we must have $x < a$ ; likewise, if $y > b$ , we know $x > b$ , so we don't need to roll more. If $y \in [a,b]$ , then we do need to roll more; roll once more and repeat.

Yes, this has the chance of going indefinitely, but it occurs with zero probability. Almost surely you will stop, and for practical purposes you should stop well before, say, 100 rolls.

This is the same idea of generating a probability of, say, 1/3 using just a standard coin. A coin is a two-sided die with faces 0 and 1; generate a binary number. When your tosses form a binary number that, whatever the remaining digits will be, is guaranteed to fall on one side or another of 1/3, you can say you're done.

Ivan Koswara - 4 years, 3 months ago

That's fairly interesting.

Since the stopping condition depends on $y$ , I would still argue that he can't choose such a random number, but I had obviously not noticed that the event $X < y$ can be determined by a discrete approximation for $X$ .

Thanks!

Brian Moehring - 4 years, 3 months ago

@Brian Moehring –

Yes, this has the chance of going indefinitely, but it occurs with zero probability

This is the idea of Kolmogorov Zero One Law (again in measure theory), which says that a tail event will either almost surely happen, or almost surely not happen.

Calvin Lin Staff - 4 years, 3 months ago

(This goes into measure theory.)

Technical note: Given a probability density function, it need not be true that "the case $x = u$ occurs with probability zero.

What you are describing is the pdf of a continuous random variable.

Calvin Lin Staff - 4 years, 3 months ago

Hrmmm? In my experience, we only talk about "densities" (with no further specification) when the cumulative distribution function is differentiable in the classical sense, so it would automatically be a continuous random variable.

Is this notation not universal?

Brian Moehring - 4 years, 3 months ago

It's unfortunate that the term "probability distribution function" applies to both discrete RV and continuous RV.

Though these concepts seem distinct, these ideas are combined in measure theory. Specifically, we use the dirac delta function , which allows for a point to have mass/area.

Calvin Lin Staff - 4 years, 3 months ago

@Calvin Lin – Certainly the concept of a Radon-Nikodym derivative allows us to define "densities" for continuous, discrete, and mixture distributions, but that's not really what I was saying. In my experience, when we talk about a density without mention of a measure, we mean a density with respect to the Lebesgue measure $\lambda$ , so from this perspective, we can only talk about a distribution possibly having a density if the distribution is continuous.

On a completely unrelated note, perhaps it's my training speaking, but I've always been wary of calling the dirac delta a "function", since it's really only defined as a functional/measure ^_^.

Brian Moehring - 4 years, 3 months ago

@Brian Moehring – In part, it depends on what kind of person you talk to, and what kind of space they work in. For a simplistic example, physicists assume that everything is nice and smooth, till things obviously break

(This starts to go into advanced measure theory. Not everyone would be able to fully comprehend this part, so don't feel discouraged.)

Radon-Nikodym is useful for probabilists to be able to split up their measure theory into 1) "continuous", 2) "discrete" and 3) "singular-continuous" parts (and exactly these 3 types). Types 1 and 2 are familiar to you, and type 3 has the property that:

$P(\{ x \} ) = 0$ ("discrete probability density function" at any point is 0)
$\{ x | P(X) \neq 0 \}$ has zero Lebesgue measure. (so if you take the integral of the "continuous probability density function", you still get 0)

An example of a singular-measure is the measure induced by the Cantor set. This is why we need the Dirac measure, which results in a "point mass", to help reconcile the probability density function of a singular-continuous probability.

Relating back to the start, for most people, treating these pdfs as continuous or discrete separately is sufficient, and they do not need the Dirac measure. For theoretical analysts (esp those that study PDE, discountinuous functions), the Dirac delta serves as a crutch to reconcile the familiar with the new. For example, to talk about introducing heat at a point, we model the heat equation with a boundary condition of the Dirac function.

Calvin Lin Staff - 4 years, 3 months ago

In the case where $x = y$ , throw a coin to decide.

Kenny Lau - 4 years, 3 months ago

Predict if this is the larger number with a probability greater than half?

1 solution

0 pending reports