All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Probability
Seeing red (Posted on 2008-06-07) Difficulty: 2 of 5

The interior of the square [0,1] x [0,1] is initially coloured white.

Four random numbers: u,v,x,y in the range [0,1] are selected and the points inside the rectangle formed by the corners (u,v), (x,y), (u,y), (x,v) are recoloured: areas painted white are repainted red, and areas painted red are repainted white.

This recolouring procedure is repeated N times. Show that the expectation value of the red area is given by the formula:

1/2 - 1/2 ∫ dA ∫ dB {1 - 2 A (1-A) B (1-B)}N

where both integrals go from 0 to 1.

  Submitted by FrankM    
No Rating
Solution: (Hide)

Because of the symmetric roles of (u,x) and (v,y) we can without loss of generality assume that u < x and v < y. A point (A,B) interior to the square will lie within the rectangle defined by the random numbers u,v,x,y if and only if

u < A < x and v < B < y

Now the probability that u < A is given by A, and the probability of A < x is given by (1-A). Hence, the probability that (A,B) lying in the given rectangle is Θ = A(1-A)B(1-B). Let PN(A,B) be the probability that a point (A,B) is painted red after N recolourations. Then (A,B) must lie within an odd number of rectangles, so

PN(A,B) = N Θ (1 - Θ)N-1 + {N (N-1) (N-2)/6} Θ3 (1 - Θ)N-3 + ..

I.e. PN(A,B) is the sum of the odd numbered terms in the binomial expansion of [(1 - Θ) + Θ]N. But

[(1 - Θ) + Θ]N = (1 - Θ)N + N Θ (1 - Θ)N-1 + {N (N-1)/2} Θ2 (1 - Θ)N-2 + {N (N-1) (N-2)/6} Θ3 (1 - Θ)N-3 + ..

[(1 - Θ) - Θ]N = (1 - Θ)N - N Θ (1 - Θ)N-1 + {N (N-1)/2} Θ2 (1 - Θ)N-2 - {N (N-1) (N-2)/6} Θ3 (1 - Θ)N-3 + ..

So PN(A,B) = [1 - (1 - 2 Θ)N]/2

The measure of the red area is then computed by integrating PN(A,B) over the square.

Comments: ( You must be logged in to post comments.)
  Subject Author Date
re: error in solutionHarry2009-03-19 20:00:02
re(2): error in solutionEigenray2008-06-10 19:53:05
Questionre: error in solutionFrankM2008-06-10 12:28:17
error in solutionEigenray2008-06-09 16:26:14
Some ThoughtsPower in independenceGamer2008-06-08 21:43:26
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (7)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2014 by Animus Pactum Consulting. All rights reserved. Privacy Information