5 ms·

What was the closed form expression for the number of rabbits?

by redcan 13y ago

anvarik 13y ago
Am also curious.
benjaminwootton 13y ago
I've made a good living as a programmer for a decade now, and I'm not afraid to say I don't even understand the question. It's a silly question unless it's for a quantitative role.
- duiker101 13y ago
  Thank god I am not alone...
- agibsonccc 13y ago
  Edit: Redacted: left for consistency. Had him confused there. A closed form expression is basically just a mathematical function used to model a potentially infinite series. Take a look here: http://en.wikipedia.org/wiki/Closed-form_expression http://en.wikipedia.org/wiki/Closed-form_expression Look at the first and second examples. You'll see the big summation sign (for loop: i to infinite) and then an explicit function. If you want to think, what the heck is this math crap used for: think about a more basic everyday concept like recursion. How do you know it will terminate?
  - pmelendez 13y ago
    I don't think he is talking about the closed form expression (at least I know what a closed-form is and still couldn't understand the question). There was no information whatsoever about what changes on each iteration... if nothing changes then the answer would be a constant of whatever rabbits were at the beginning... and that doesn't sound about right :/
    - agibsonccc 13y ago
      Bah got ya.
- tjbiddle 13y ago
  Good to hear. I'm working as a Jr. Software Engineer now, and I don't consider mathematics one of my strong points. Do many positions actually expect people to know these kinds of questions? I'd crash and burn here.
peter-fogg 13y ago
It's underspecified anyway -- we need to know about the motion of rabbits, the troll, the density of black holes, etc.
arethuza 13y ago
In that context I'd be really tempted to ask why they needed a closed form expression for the number of rabbits...
- raverbashing 13y ago
  Yes But my bet would be zero, if the troll has infinite time
dferlemann 13y ago
I don't think the question is complete... otherwise I probably just give: x => Num of Rabbits, y => Num Holes x,y,x+y=[0,m*n-1]
konstantintin 13y ago
probaby not right... E(number_of_rabbits) = rabbits_in_last_turn - prob(land on rabbit) - sum_i_to_infinity(prob(land_on_blackhole)^i*prob(land on rabbit))
- pmelendez 13y ago
  This is not a closed form thought... (although it sounds about right)
kdavis 13y ago
My guess is that you'd model the troll as a 2D simple symmetric random walk with the rabbits and black holes stationary and distributed randomly with some densities R and B. As a first go I'd assume that the topology was that of a torus, so as to not deal with the boundary. Now, as the exact definition of a "round" wasn't specified, I'll just assume the troll can walk forever. Now, it's been proven that a simple symmetric random walk on a 2D lattice has probability 1 of reaching any given point as the number of steps goes to infinity. So, ignoring the teleporting, the closed form answer for the number of rabbits eaten is mnR. With teleporting, I'd guess the Markov chain would mix better. So, the closed form answer would again be mnR.
mattemattematte 13y ago
I'll give it a try... The number of rabbits at the (i+1)'th step is equal to the number of rabbits at the i'th step minus that one rabbit which is /maybe/ being eaten. And the "maybe" I think can be quantified as the probability the Troll has to find a rabbit at the i'th step. So: R_(i+1) = R_i -1 * P(Troll finds a rabbit) And now we have to calculate the probability of the event "Troll finds a rabbit" (i'll call it event A). There are 2 cases: * the Troll falls into a black hole (btw, i'm gonna assume the blackholes teleport to any cell with uniform probability); * the Troll does not fall into a black hole; I'm going to call these two events B and not(B). So: P(A) = P(A given B) + P(A given not(B)) Well, P(A given B) is the probability that Troll is being teleported to a cell with a rabbit in it, that is number of rabbits over number of cells: R_i / (nm) P(A given not(B)) is the probability that Troll will step on a rabbit in a nearby cell which is: rabbits' density over 8: R_i / (8nm) So: R_(i+1) = R_i - ( R_i/nm + R_i/8nm ) = R_i * ( 1 - 9/8nm ) = ... iterating ... = R_0 * ( 1 - 9/8nm )^i R_0 being the initial number of rabbits. I'm not sure all this is correct, but that formula confirms the following intuitions: * The number of rabbits is monotonically decreasing at every step; * The bigger the grid, the slower the decrease. edit: The closed formula would be: int numOfRabbits(int numOfSteps) { if (numOfSteps == 0) return R_0; else return R_0 * (1 - 9/8nm)^(numOfSteps-1); }
- deleted 13y ago
  [deleted]

What was the closed form expression for the number of rabbits?

by redcan 13y ago

What was the closed form expression for the number of rabbits?

anvarik 13y ago

Am also curious.

benjaminwootton 13y ago

I've made a good living as a programmer for a decade now, and I'm not afraid to say I don't even understand the question. It's a silly question unless it's for a quantitative role.

duiker101 13y ago
Thank god I am not alone...
agibsonccc 13y ago
Edit: Redacted: left for consistency. Had him confused there. A closed form expression is basically just a mathematical function used to model a potentially infinite series. Take a look here: http://en.wikipedia.org/wiki/Closed-form_expression http://en.wikipedia.org/wiki/Closed-form_expression Look at the first and second examples. You'll see the big summation sign (for loop: i to infinite) and then an explicit function. If you want to think, what the heck is this math crap used for: think about a more basic everyday concept like recursion. How do you know it will terminate?
- pmelendez 13y ago
  I don't think he is talking about the closed form expression (at least I know what a closed-form is and still couldn't understand the question). There was no information whatsoever about what changes on each iteration... if nothing changes then the answer would be a constant of whatever rabbits were at the beginning... and that doesn't sound about right :/
  - agibsonccc 13y ago
    Bah got ya.
tjbiddle 13y ago
Good to hear. I'm working as a Jr. Software Engineer now, and I don't consider mathematics one of my strong points. Do many positions actually expect people to know these kinds of questions? I'd crash and burn here.

peter-fogg 13y ago

It's underspecified anyway -- we need to know about the motion of rabbits, the troll, the density of black holes, etc.

arethuza 13y ago

In that context I'd be really tempted to ask why they needed a closed form expression for the number of rabbits...

raverbashing 13y ago
Yes But my bet would be zero, if the troll has infinite time

dferlemann 13y ago

I don't think the question is complete... otherwise I probably just give: x => Num of Rabbits, y => Num Holes x,y,x+y=[0,m*n-1]

konstantintin 13y ago

probaby not right... E(number_of_rabbits) = rabbits_in_last_turn - prob(land on rabbit) - sum_i_to_infinity(prob(land_on_blackhole)^i*prob(land on rabbit))

pmelendez 13y ago
This is not a closed form thought... (although it sounds about right)

kdavis 13y ago

My guess is that you'd model the troll as a 2D simple symmetric random walk with the rabbits and black holes stationary and distributed randomly with some densities R and B. As a first go I'd assume that the topology was that of a torus, so as to not deal with the boundary. Now, as the exact definition of a "round" wasn't specified, I'll just assume the troll can walk forever. Now, it's been proven that a simple symmetric random walk on a 2D lattice has probability 1 of reaching any given point as the number of steps goes to infinity. So, ignoring the teleporting, the closed form answer for the number of rabbits eaten is mnR. With teleporting, I'd guess the Markov chain would mix better. So, the closed form answer would again be mnR.

mattemattematte 13y ago

I'll give it a try... The number of rabbits at the (i+1)'th step is equal to the number of rabbits at the i'th step minus that one rabbit which is /maybe/ being eaten. And the "maybe" I think can be quantified as the probability the Troll has to find a rabbit at the i'th step. So: R_(i+1) = R_i -1 * P(Troll finds a rabbit) And now we have to calculate the probability of the event "Troll finds a rabbit" (i'll call it event A). There are 2 cases: * the Troll falls into a black hole (btw, i'm gonna assume the blackholes teleport to any cell with uniform probability); * the Troll does not fall into a black hole; I'm going to call these two events B and not(B). So: P(A) = P(A given B) + P(A given not(B)) Well, P(A given B) is the probability that Troll is being teleported to a cell with a rabbit in it, that is number of rabbits over number of cells: R_i / (nm) P(A given not(B)) is the probability that Troll will step on a rabbit in a nearby cell which is: rabbits' density over 8: R_i / (8nm) So: R_(i+1) = R_i - ( R_i/nm + R_i/8nm ) = R_i * ( 1 - 9/8nm ) = ... iterating ... = R_0 * ( 1 - 9/8nm )^i R_0 being the initial number of rabbits. I'm not sure all this is correct, but that formula confirms the following intuitions: * The number of rabbits is monotonically decreasing at every step; * The bigger the grid, the slower the decrease. edit: The closed formula would be: int numOfRabbits(int numOfSteps) { if (numOfSteps == 0) return R_0; else return R_0 * (1 - 9/8nm)^(numOfSteps-1); }

deleted 13y ago
[deleted]