Interesting probability problem

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

User avatar
measure
Posts: 80
Joined: Sat Apr 04, 2015 4:31 pm UTC
Location: Time-traveling kayak

Interesting probability problem

Postby measure » Tue Apr 25, 2017 8:55 pm UTC

Here's a problem that was bugging me for a while. I was going to post it here for help, but I ended up solving it myself. I thought the solution looked kinda pretty, so I decided to post it here for y'all:

Suppose a value x is chosen at random uniformly on the interval [0,1]. Next two numbers a and b are chosen at random uniformly on the interval [0,x]. You are then told the absolute value of the difference of a and b δ=|a-b|. Given δ, what is the expected value of x?

Here is a python program I wrote to run a bunch (10^7) of trials and plot for each δ the average of the x values that resulted in that δ:
Spoiler:

Code: Select all

import random

steps = 1000
trials = 10000000
sd = []
cd = []

for i in range(steps):
   sd.append(0)
   cd.append(0)

for i in range(trials):
   x = random.uniform(0,1)
   a = random.uniform(0,x)
   b = random.uniform(0,x)
   d = abs(a-b)
   pd = int(steps*d)
   sd[pd] += x
   cd[pd] += 1

for i in range(steps):
   if cd[i] > 0:
      print("> d = "+str(i/steps)+"\t("+str(cd[i])+")\tavg(x) = "+str(sd[i]/cd[i]))
      #print(i/steps,sd[i]/cd[i])
   else:
      print("> d = "+str(i/steps)+"\t(0)")
      #print(i/steps)

My solution:
Spoiler:

Code: Select all

_      δ*ln(δ) - δ + 1
x(δ) = ―――――――――――――――
        -ln(δ) + δ - 1

User avatar
Xanthir
My HERO!!!
Posts: 5186
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Interesting probability problem

Postby Xanthir » Thu Apr 27, 2017 7:02 pm UTC

Not looking at your solution yet, but I know from prior experience that the average distance between two uniformly-random points in an interval is 1/3 the length of the interval, so I believe I can just reverse that - E(x)=3δ.

Now I've looked at your trials, and: interesting!
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

User avatar
measure
Posts: 80
Joined: Sat Apr 04, 2015 4:31 pm UTC
Location: Time-traveling kayak

Re: Interesting probability problem

Postby measure » Fri Apr 28, 2017 1:15 pm UTC

Xanthir wrote:Not looking at your solution yet, but I know from prior experience that the average distance between two uniformly-random points in an interval is 1/3 the length of the interval, so I believe I can just reverse that - E(x)=3δ.

Yeah, that was my first thought as well. Remember though that x is capped at 1 and δ can be as large as 1 as well. (I think the average of δ/x does end up being 1/3, but that's just a first-order approximation, and I don't think in general the reciprocal of the average will be the average of the reciprocals.)

User avatar
cyanyoshi
Posts: 356
Joined: Thu Sep 23, 2010 3:30 am UTC

Re: Interesting probability problem

Postby cyanyoshi » Sat Apr 29, 2017 11:47 pm UTC

I got the same answer as measure. Seems like using Bayes' theorem and a lot of handwaving usually works!

User avatar
measure
Posts: 80
Joined: Sat Apr 04, 2015 4:31 pm UTC
Location: Time-traveling kayak

Re: Interesting probability problem

Postby measure » Sun Apr 30, 2017 1:40 pm UTC

cyanyoshi wrote:I got the same answer as measure. Seems like using Bayes' theorem and a lot of handwaving usually works!

I tried to get it to work with Bayes' theorem, but I didn't trust my handwaving to apply it to continuous distributions. I ended up going with a geometric/calculus approach.

User avatar
cyanyoshi
Posts: 356
Joined: Thu Sep 23, 2010 3:30 am UTC

Re: Interesting probability problem

Postby cyanyoshi » Sun Apr 30, 2017 11:54 pm UTC

My intuition is that with random variables X, Y and Z, then you can get everything you need from the pdf f(x,y,z). By normalizing f(x,y0,z0), it seems that you should get f(x|y0,z0), the conditional probability distribution of X given that Y=y0 and Z=z0. Clearly, f(a,b|x0) should be constant over the square (a,b)∈[0,x0]2, so f(a,b|x0)=1/(x0)2. I am visualizing the domain of f(a,b,x) as an inverted pyramid with its vertex at (0,0,0) and its base is a square with vertices (0,0,1), (1,0,1), (1,1,1), and (0,1,1). Each horizontal slice should be a square with the same infinitesimal "mass" of dx. So then f(a,b,x) = 1/x2 within this pyramid and is zero elsewhere.

OK, now what about f(δ,x)? Fixing X=x0 again, f(a,b|x0) is just a uniform distribution over a square. My gut tells me that f(δ|x0) is proportional to the length of the level curve of δ(a,b) = |a-b| in this domain. This is just C*2*sqrt(2)*(x0-δ). Normalizing over the domain [0,x] gives f(δ,x)=2*(x-δ)/x2.

Now then, f(x|δ)=C*2*(x-δ)/x2. x can take any value in [δ,1], so this must integrate to 1 over that interval. Doing the integral makes C=2*δ-2-2*ln(δ). Now we got f(x|δ) = 1/(δ-1-ln(δ))*(x-δ)/x2. The expected value of x under this pdf is the integral of x*f(x|δ) on the interval of all possible x values, namely [δ,1]. Thus the expected value of x given δ is (1-δ+δ*ln(δ))(δ-1-ln(δ)).


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 9 guests