Sunday, February 20, 2011

Fox 329

E[R] below can be computed depending on the random process... Try to guess what it is before computing. Randomness may be a fancy business...
See a similar concept: Bertrand Paradox


Dervish Fox: How can you cut a square randomly?

Red Fox:
Here is a way; first generate a random number to represent point A. Then another random number for point B along the three others sides. Drawn the line AB, and cut it out.

Dervish:
And how can you generate a random number?

Red:
Excel does it easily. Type "=RAND()", and boom, you get one right away.

Dervish:
But that depends on some seed numbers in the machine's memory, no?

Red:
Yes, that's why they call them pseudo-random numbers. Do you have a problem with that?

Dervish:
I have a bigger problem than that.

Red:
So... you believe that random numbers can't exist.

Dervish:
I believe that the word "random" should be removed from all world dictionaries.

Red:
Radical.

http://www.8foxes.com/

12 comments:

  1. I have a problem with this one too. How can one cut a square randomly? The process as described by the Red Fox is basically: generate two random numbers (Let's ignore Dervish's objection at this time), point A is uniformly distributed in one side, while the point B is uniformly distributed in the other three sides. Now does that really constitute a random cut?? I am not so sure.

    How about the following process:
    generate two random numbers to identify an interior point in the square. Then generate a random angle (or slope). draw the line passing thru the interior point with the generated angle (say with the horizontal). Does this process cut a square randomly?

    More importantly, do both processes reveal the same answer? Maybe not.

    -Polar Fox

    ReplyDelete
  2. I'm afraid to post my answer for several reasons. Probability isn't my greatest strength, but I will tell you what I have, and perhaps I can combine my answer with Henkie's well done solution to the other similar problem.

    WLOG, I assumed that the square was with length 1, and I assumed that point A is on the bottom line (as depicted in the drawing). I looked at all possible lines that cross the left side and the bottom side (because of symmetry, I didn't need to bother with the right side). And I came up with 7/4 being the expected value. I will show the proof later if necessary, but essentially what you will do is double integrate f(x,y)xy dxdy from 0 to 1 on both integrals.
    f(x,y) actually is (2-xy)/xy, so the xy cancels out.

    Now this is the expected value of all possible lines crossing the bottom line with either side. From Henkie's solution, we know that the expected value of all lines crossing the top with the bottom side is 3. So I'm pretty certain the expected value of the whole thing will be near 3. It seems like you may can just average the two together and get 3.875, but I highly doubt that's correct. I don't know, any suggestions?

    ReplyDelete
  3. Correction: Not 3.875, but 2.375.

    Also, I guess my final answer will be that you are twice as likely to have a line cross one of the sides with the bottom rather than the top to bottom; therefore "I think" the answer should be (2/3)*(7/4) + (1/3)*3 = 13/6

    ReplyDelete
  4. assuming the random process described by red fox:
    E[R]=1/3 (bottom, top) + 2/3 (bottom, side)
    =1/3 *(henkie's) + 2/3 (b,s)
    = 1 + 2/3 (b,s)

    i think (b,s) can be a higher number than your computation (7/4). i'll try later...

    ReplyDelete
  5. Let me post my solution and see what you think.

    ReplyDelete
  6. WLOG, assume the square sides each have length 1. Also, I will only be working with the left side and bottom side. Call the random variable generated on the bottom side x, and call the random variable generated on the left side y. The area on the left side of the line is always less than the area on the right side, therefore the function we want is of the equation
    f=(1-A)/A, where A is the area of the left side. A = xy/2

    -> f = (2-xy)/xy

    Expected Value = double integral xy*(2-xy)/xy dxdy (both x,y go from 0 to 1.

    Expected Value = 7/4

    ReplyDelete
  7. yes that integral gives 7/4. but (bottom,side) cut must rrsult in a much much bigger ratio of bigger area to smaller area. E[R] in this case must be much bigger.
    if E[b,s]=7/4, then the result:
    E[R]=1 + 2/3 * 7/4 = 2.166 < 3.
    this doesn't make sense. henkie's solution: cutting E[bottom-top] is greater than this random cut.
    something's fishy.....

    ReplyDelete
  8. a microsoft excel simulation of this problem with more then 20 million instances gives the following:
    average R = 345.5
    sdtev is very high: more than 40000.

    can the answer be infinity?

    ReplyDelete
  9. Ah yes, I see your point. I think I was supposed to take the integral from 1 to infinity (i.e. sample space). If this were the case, then the integral doesn't absolutely converge, which means it doesn't have an expected value.

    ReplyDelete
  10. Due to a possible error in blogspot, Bleaug was not able to post the following comment yesterday:

    -----------

    now we're getting somewhere...

    for those who don't know Bertrand paradox already, have a look at http://en.wikipedia.org/wiki/Bertrand_paradox_%28probability%29

    Basically what this paradox says is that the expected value of some variable in a multidimensional system depends on how the randomness of samples is defined. In other words, there is no absolute definition of a "fair random secant" for a square (nor for a circle as in original Bertrand Paradox statement).

    This means that if we compute R ratio average for N samples, we must weigh each sample with some probability density function which depends on the way the random secant is chosen.

    Main difference lies in the fact that here the variable (ratio R) is unbounded, whereas in Bertrand Paradox statement, secant length is bounded.

    Let's take an extreme example: only consider secants parallel to Ox axis, cutting Oy at y chosen at random in [0,1]. It is easy to see that expected value for R does not exist because of divergence of integral of (1-y)/y.

    The divergence you observe with your 20 million samples exercise is the direct consequence of this unboundness, because of the "randomness procedure" hinted at in problem statement. The more samples, the higher average and standard deviation you get.

    Now, let's define a probability density function P as follows:
    - for each secant S let M(S)=(mx, my) be its midpoint
    - let d(S)=min(mx, 1-mx, my, 1-my), i.e. the distance to square border
    - P(S)=3.d(S)

    P is normalised: integral over the unit square is equal to 1. If you weigh each sample with this density when averaging, you should get a convergent value (around 4.30 in my tests).

    Bottom line is that there is no answer to the problem. If "random secant" procedure is formally defined, it may or may not yield a convergent value, and if convergent the value may be any value depending on the choice of probability density function...


    sorry for the lengthy post ;-)

    bleaug

    ReplyDelete
  11. Thank you for the information Bleaug. What Bertrand says in his paradox is identical to what Polar Fox commented out at the beginning. A link to the Paradox should be given in the problem text.

    Yes, yes, a higher council should define -meticulously define- a random cut. Oh by the way, Dervish goes even deeper; how can you generate random numbers while everything depends one another? Let's ignore him for the time being.

    But... if our random-cut is as defined by Red Fox (point A is random in one side, and B is random along other 3), then our work here shows that the expected ratio, E[R], WON'T CONVERGE. Although the options kinda imply that, let me still add that most accurate answer, too.

    Non-convergence makes sense here, because Red's cut gives more precedence to side cuts, which may push E[R] to oblivion.

    We could have found a converging value, had we defined a different random process. See Henkie's solution for Fox 324 as an example.

    This has been a good exercise for us to understand randomness a little better.

    ReplyDelete
  12. How can you
    understand something
    which doesn't even exist?

    How can you
    swim in an ocean
    that "never been"?

    You define,
    you assume,
    you make it up.
    then climb up your tower,
    built up by nothing but
    assumption and axioms.

    Stay until it tumbles down
    with the next wind.

    It is then you who remains,
    and the sand,
    and the wind that drifts it away.
    Good luck next time.

    -Dervish Fox

    ReplyDelete