Wikipedia:Reference desk/Archives/Mathematics/2023 July 21

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

July 21

What is the expected number of steps it will take to reach the exit square of this teleporting grid?

(This is a question inspired by and abstracted from various adventure computer games involving navigating a map of rooms.)

Consider a grid of squares. The grid has total width W and total height H. You start on an entrance square in the lower-left or southwestern corner. Your goal is to reach an exit square in the fewest steps possible, where a "step" means to move orthogonally (vertically or horizontally only; diagonal moves are not allowed) into an adjacent square.

If the exit square is in the top-right or northeast corner, this would take W + H - 2 steps: you would move W - 1 steps to the right/east, and then H - 1 steps to the top/north to reach the exit square, for a total of W + H - 2 steps.

But, there is a twist: whenever you take a step, there is a constant probability P that you will be teleported to a random square instead of to the square you were trying to step to.

The two parts to my question:

(1) In terms of W, H, and P, what is the expected number of steps to reach that exit square in the top-right corner?

(2) Same question, but now W and H are both guaranteed to be odd, and the exit square is now the center square of this grid rather than the top-right/northeast square of this grid.

—SeekingAnswers (reply) 06:28, 21 July 2023 (UTC)

Just to clarify. does the random square (that we might be teleported to) include:

• the square where we came from?
• the square that we wanted to step to anyway?
• the origin square?
• the final destination square? (which might cause to win in one step, among other possibilities, with a probability of p/(w*h-x) (where x depends on the answer to this question))
• or none of the above?

Note: I see that you also posted at https://math.stackexchange.com/questions/4739893/what-is-the-expected-number-of-steps-it-will-take-to-reach-the-exit-square-of-th Dhrm77 (talk) 11:22, 21 July 2023 (UTC)

Excellent questions; I realize I was unclear on those points! Many of the games I was playing seem to have additional code preventing the teleportation from being to some of the four types (which types are avoided varies depending on the game) of squares you specified, but the math is probably easier not having to deal with those exceptions. I'd be interested in all types of answers, both those with or without dealing with any of those exceptions. —SeekingAnswers (reply) 16:11, 21 July 2023 (UTC)

Ok. Are you looking for a accurate math equation, or an approximation? If you are looking for an approximation, I wrote a simulation, for problem 1, assuming no exceptions, and from the results, I got this equation that approximates the answer:

• number of steps ≈ H + W - 2 + P² * (H-P) * (W-P), P being the odds of jumping, so for 50%, P=0.5
• For example for W=3, H = 5, P = 0.25, you get about 6.81 steps. My simulations gives me 6.91 steps.

For a higher precision you would need the equation to be quadratic, or do the actual math, integrating an infinite series, and that might be challenging.

for problem 2, I haven't tried, but I am guessing the answer is probably a little less than half of problem 1. Dhrm77 (talk) 19:25, 21 July 2023 (UTC)

Exact answers are what I'm interested in. I'm interested in seeing what the formula would be and how it would be derived. —SeekingAnswers (reply) 20:42, 21 July 2023 (UTC)

Let us generalize a bit. We have a finite set $S$ of token positions and a target position $t\in S.$ We also have a distance function $\delta :S\times S\to \mathbb {N}$ (although we are actually only interested in $\delta (s,t),s\in S$), When $S=\{0,...,W{-}1\}\times \{0,...,H{-}1\}$ and $t=(0,0),$ and the token can only move horizontally and vertically, we have $\delta ((i,j),t)=i+j$ (the Manhattan distance).

The expected number of steps from a given position does not depend on the precise position but on its distance $d$ from $t.$ We denote the value, given $d,$ by $E(d).$ Let $X\in \mathbb {Q}$ denote the (unknown) expected number of steps from a randomly chosen position in $S,$ where all positions have equal probability. Then we can define $E(d)$ recursively:

$E(0)~~~~~=0\,$;

$E(d{+}1)=1+PX+(1{-}P)E(d)$.

An uninteresting calculation shows that the recursive definition has the following explicit solution:

$E(d)=(1+PX)(1-(1{-}P)^{d})/P.$

(If $P=0,$ replace this by $E(d)=d.$)

$X$ equals the average value of $E(d),$ averaged over all positions:

$X={\frac {1}{|S|}}\sum _{s\in S}E(\delta (s,t)).$

By rewriting the symbolic sum as an explicit sum $E(\delta (s_{1},t))+...+E(\delta (s_{n},t)),$ replacing each $\delta (s_{i},t))$ by its numerical value, unfolding each application of $E(\cdot )$ by the rhs of the definition, and collecting like terms, we obtain a linear equation of the form

$X=aX+b.$

Plugging its solution $X=b/(1{-}a)$ into the definition of $E(d)$ gives us an explicit closed form that can be computed directly and exactly.  --Lambiam 16:42, 22 July 2023 (UTC)

The meaning of $f(x)/x$

In calculus, for every smooth function $f(x)$ there exists a clear meaning of ${\frac {df}{dx}}.$ It's simply the derivative of $f$ at $x$, i.e. the slope of the tangent of the graph of $f$ at $x.$

For every given smooth function $f$, does also the expression ${\frac {f(x)}{x}}$ have an intuitive meaning, in any branch of mathemstics? 2A06:C701:7471:3000:39AA:1A85:25C2:975B (talk) 12:50, 21 July 2023 (UTC)

It's the slope of the line that goes through the origin and the point $(x,f(x))$. --Wrongfilter (talk) 12:52, 21 July 2023 (UTC)

Resolved

2A06:C701:7471:3000:39AA:1A85:25C2:975B (talk) 13:02, 21 July 2023 (UTC)

It is also the average rate of change of ƒ with respect to its input in the part of the range where the input is between 0 and x. Michael Hardy (talk) 21:24, 21 July 2023 (UTC)