Paseo aleatorio en los bordes de un cubo.

35

Una hormiga se coloca en la esquina de un cubo y no puede moverse. Una araña comienza a partir de la esquina opuesta, y pueden moverse a lo largo de los bordes del cubo en cualquier dirección (x,y,z) con igual probabilidad 1/3 . En promedio, ¿cuántos pasos necesitará la araña para llegar a la hormiga?

(Esto no es tarea, fue una pregunta de entrevista).

Elizabeth Susan Joseph
fuente
77
¿Deberes? ¿Qué has intentado hasta ahora?
Adrian
Con respecto a las cadenas de Markov, aquí hay una gran introducción setosa.io/blog/2014/07/26/markov-chains
DL Dahly
1
Normalmente, este tipo de trabajo de rutina debe estar marcado con la self-studyetiqueta y seguir las pautas en su etiqueta wiki . Edite esta pregunta e
inclúyala
44
@GarethMcCaughan - No, fue una pregunta de entrevista.
Elizabeth Susan Joseph
Siguiendo @alesc hice un Plunker de JavaScript. plnkr.co/edit/jYQVDI
abbaf33f

Respuestas:

32

Sugiero modelar el problema como una cadena de Markov donde cada estado representa la distancia entre la araña y la hormiga. En este caso tenemos 4 estados posibles Si ya que las distancias i puede ser {0,1,2,3} .

Cuando la araña está en la esquina opuesta del cubo, está a una distancia de 3 pasos de la hormiga. Está en el estado S3 .

La construcción de la matriz de transición P .

  • Si dibujamos un cubo, vemos que cuando estamos en el estado , cada movimiento reduce la distancia entre la araña y la hormiga a 2 pasos. Entonces, cuando estamos en el estado S 3, pasamos al estadoS3S3 con probabilidad 1.S2

  • Cuando estamos en el estado , podemos volver al estado S 3 utilizando el borde al que llegamos desde allí o podemos disminuir la distancia a solo un paso si elegimos otros dos bordes. Entonces, cuando estamos en el estado S 2 podemos pasar al estado S 1 con probabilidad 2/3 y al estado S 3 con probabilidad 1/3.S2S3S2S1S3

  • Cuando estamos en el estado , podemos ir al estado S 0 usando uno de los tres bordes posibles. Si usamos los otros dos, volvemos al estado S 2 . Entonces, cuando estamos en el estado S 1 podemos pasar al estado S 0S1S0S2S1S0 con probabilidad 1/3 y al estado con probabilidad 2/3.S2

  • Cuando llegamos al estado , nos quedamos allí ya que es nuestro objetivo. S 0 es un estado absorbente.S0S0

P=[PS3S3PS3S2PS3S1PS3S0PS2S3PS2S2PS2S1PS2S0PS1S3PS1S2PS1S1PS1S0PS0S3PS0S2PS0S1PS0S0]=[01001/302/3002/301/30001]

This is an absorbing Markov chain with three transient states (S3, S2, S1) and one absorbing state (S0).

According to the theory, the transition matrix of a Markov chain with t transient states and r absorbing states can be rewritten as:

P=[QtR0r×tIr]

where Qt is a t×t matrix that shows the probability of transitioning from some transient state to another transient state, while R is a t×r matrix with the probabilities of transitioning from one of the t transient states to one of the r absorbing states. The identity matrix Ir shows us that when any of the r absorbing state is reached, there is no transition away from that state. The all zeros matrix 0r×t can be interpreted as that there is no transition from any of the r absorbing states to any of the t transient states.

The (i,j) entry of Qt represents probability of transitioning from a state i to a state j in exactly one step. To get the probability for k steps we need the (i,j) entry of Qtk. Summing for all k, we get a matrix that contains in its (i,j) entry the expected number of visits to transient state j after starting from transient state i.

k=0Qtk=(ItQt)1

To get the number of steps until being absorbed, just sum the values of each row of (ItQt)1. This can be represented by

t=(ItQt)11

where 1 is a column vector with all components equal to 1.

Let us apply this to our case:

As stated above, in our case we have t=3 transient states and r=1 absorbing state, therefore:

Qt=[0101/302/302/30]R=[001/3]

The matrix with the expected number of visits is

(ItQt)1=[2.54.531.54.53133]

This matrix can be interpreted as follows. Starting from state S3 and before getting absorbed at S0 we visit, on average, S3 2.5 times, S2 4.5 times, and S1 3 times.

The expected number of steps from state S3 to state S0 is given by the first component of the following vector:

t=[2.54.531.54.53133][111]=[1097].

The second and third components of t are the expected number of steps to S0 if we start from S2 and S1 respectively.

tiagotvv
fuente
I have no idea what mcmc is . I have to read it and then check your solution. Is there any good mcmc explanation that compliments your solution?
Elizabeth Susan Joseph
10
@ElizabethSusanJoseph Note that Markov chains and MCMC (Markov chain Monte Carlo) are two distinct concepts (although MCMC is based on Markov chains). This answer does not use MCMC for anything. So you are probably searching for a good explanation about Markov chains, not about MCMC.
Juho Kokkala
tiagotvv your explanation would be improved by defining and explaining the use of the transition matrix P, the meaning of the quantity r, and the height of the column vector. Bonus points for meaning of subsequent elements of the vector t. :)
Alexis
@JuhoKokkala - thanks I will then look at the markov chain explanations.
Elizabeth Susan Joseph
@Alexis I added some explanation regarding the matrices and vectors.
tiagotvv
21

Let x be the number of expected steps. Let x1 be the number of expected steps from any corner adjacent to the origin of the spider and x0 ditto for the ant.

Then x=1+x1 and x0=1+23x1

x1=1+23x0+13x=1+23x0+13+13x1

x1=x0+2x0=1+23x0+43 implying that x0=7 and x1=9.

We get our answer as x=10.

Edit:

If we draw the cube with coordinates (x,y,z) then 111 is the starting position of the spider and 000 the position of the ant.

The spider can move to either 011, 101 or 110.

By the symmetry of the cube these must have the same number of expected steps to the ant, denoted by x1. From x1, we can either return to the origin (with probability 1/3) or (with probability 2/3) we can go to one of the points 001, 100, 010 depending on which state we are in.

Again, by symmetry, these points will have the same number of expected steps which we call x0. From these positions we can reach the goal in one step with probability 1/3 or go back to one of the x1-positions with probability 2/3. This means that x0=131+23(1+x1)=1+23x1.

Hunaphu
fuente
Could you further elaborate your answer? Please explain in layman terms :)
Elizabeth Susan Joseph
17

One nice abstraction to think of it is this:

Think of the Position of the Ant as (0,0,0) and Spider (1,1,1), now each move the spider can make will essentially switch exactly one of the three components from 10 or 01. So the question becomes:

If I randomly switch bits in (1,1,1) after how many steps in average do I get 0,0,0

We see the shortest way is 3 switches. Since it doesn't matter with which bit I start the probability of that happening is 1 * 2/3 * 1/3 = 2/9. If we make 1 mistake (switch one bit back to 1) we will need 5 steps. And the chances of making a mistake are 7/9 - if we want to make only one mistake, we have to get from there back and do everything right again - so the chance of making exactly 1 mistake resulting in 5 steps is 7/9 * 2/9 and the chance of making 2 mistakes aka 7 steps is (7/9)² * 2/9 and so on.

So the formula for the expected average number of steps is:

E(steps)=n=0(3+2n)29(79)n=10
Falco
fuente
Your solution is some what confusing. What is this formula? what is n here?
Elizabeth Susan Joseph
5
It is actually the shortest and cleanest solution. The solution is in the form of an infinite sum of numbers from zero to infinity and n is the current integer in that infinite sum.
alesc
This is really nice! My answer is similar, but breaks up the sequence of switches into pairs - which lets me expectate a geometric variable (or alternatively, sum a geometric series) rather than sum an arithmetico-geometric series. That's the only substantive difference: it doesn't matter much whether one takes "first three switches, then subsequent pairs" (as you did) or "first switch, then subsequent pairs" (as I did), since unless the fly is caught in 3 switches, then either way you're dealing with one odd and two even parities.
Silverfish
16

Just to compliment tiagotvv's answer:

I don't naturally think of these kinds of problems as matrices (even though they are). I have to draw it out, which I've done below. You can see that there are 3 places to move from S, all of which are As. From any A, you can either return to the S, or move to one of two Bs. From any B, you can move to the E, or to one of two As. This all translates to the transition matrix given by tiagotvv, which can also be drawn in graph form.

enter image description here

Because I am terrible at math, I would just try to simulate your problem. You can do this with the markovchain package in R.

  library(markovchain)
  library(ggplot2)

  # Create a markovchain object, given the states and their transition matrix

  mcCube <- new("markovchain", 
                states = c("S", "A", "B", "E"),
                transitionMatrix = matrix(data = c(0,   1,   0,   0,
                                                   1/3, 0,   2/3, 0,
                                                   0,   2/3, 0,   1/3,
                                                   0,   0,   0,   1), 
                                          byrow = T, nrow = 4),
                name = "cube")

  # The following code calcuates the probability of landing on E after taking
  # between 1 and 100 steps from the start, given the above set of transition
  # probabilities.

  start <- c(1, 0, 0, 0)

  list <- list()

  for (i in 1:100){

    list[[i]] <- (start * mcCube^i)[4] 

  }

   a <- do.call(rbind, list)

   data <- data.frame(propE = a, 
                      steps = c(1:100))

   ggplot(data, aes(x = steps, y = propE)) +
    geom_line(size = 1) +
    ylab("Probability you reached the spider") +
    xlab("Number of steps taken") +
    theme_bw() +
    theme(panel.grid.minor = element_blank())

enter image description here

  # This code simulates 1000 different applications of the markov chain where you 
  # take 1000 steps, and records the step at which you landed on E

  list <- list()
  for (i in 1:1000) {


    b <- rmarkovchain(n = 1000, object = mcCube, t0 = "S", include.t0 = T)

    list[[i]] <- 1001 - length(b[b == "E"])

  }

  data <- as.data.frame(do.call(rbind, list))

  ggplot(data, aes(x = V1)) +
    geom_density(fill = "grey50", alpha = 0.5) +
    geom_vline(aes(xintercept = mean(V1))) +
    ylab("Density") +
    xlab("Number of steps to reach E") +
    theme_bw() +
    theme(panel.grid.minor = element_blank())

  mean(data$V1)  # ~10 is the average number of steps to reach E in this set of
                 # simulations

enter image description here

tiagotvv's answer can be calcuated in R as:

q = matrix(c(0,   1,   0,   
             1/3, 0,   2/3, 
             0,   2/3, 0), byrow = T, nrow = 3)


(solve(diag(3) - q) %*% c(1, 1, 1))[1] # = 10
D L Dahly
fuente
11

Parity considerations give a very clean solution, using surprisingly simple machinery: no Markov chains, no iterated expectations, and only high school level summations. The basic idea is that if the spider has moved an even number of times in the x direction, it has returned to its original x coordinate so can't be at the ant's position. If it has moved an odd number of times in the x direction, then its x coordinate matches the ant's. Only if it has moved an odd number of times in all three directions will it match the x, y and z coordinates of the ant.

Initially the spider has made zero moves in any of the three directions, so the parity for each direction is even. All three parities need to be flipped to reach the ant.

After the spider's first move (let's label that direction x), exactly one direction has odd parity and the other two (y and z) are even. To catch the ant, only those two parities need to be reversed. Since that can't be achieved in an odd number of subsequent moves, from now on we consider pairs of moves. There are nine possible combinations for the first paired move:

(x,x),(x,y),(x,z),(y,x),(y,y),(y,z),(z,x),(z,y),or(z,z)

We need to move in the y and z directions to reach the ant after one paired move, and two out of nine combinations will achieve this: (y,z) and (z,y) would ensure all three parities are odd.

The other seven combinations leave one odd and two even parities. The three repeated moves, (x,x), (y,y) or (z,z), leave all parities unchanged so we still require one y and one z movement to reach the ant. The other pairs contain two distinct moves, including one in the x direction. This switches the parity of x and one of the other parities (either y or z) so we are still left with one odd and two even parities. For instance the pair (x,z) leaves us needing one more x and one more y to reach the ant: an equivalent situation (after relabelling of axes) to where we were before. We can then analyse the next paired move in the same way.

In general paired moves start with one odd and two even parities, and will either end with three odd parities (with probability 29) and the immediate capture of the ant, or with one odd and two even parities (with probability 79) which returns us to the same situation.

Let M be the number of paired moves required to reach the ant. Clearly M follows the geometric distribution on the support {1,2,3,} with probability of success p=29 so has mean E(M)=p1=92=4.5. Let N be the total number of moves required, including the initial move and the M subsequent paired moves. Then N=2M+1 so, applying linearity of expectations, E(N)=2E(M)+1=2×4.5+1=10.

Alternatively you might note P(Mm)=(79)m1 and apply the well-known formula for the mean of a discrete distribution taking only non-negative integer values, E(M)=m=1P(Mm). This gives E(M)=m=1(79)m1 which is a geometric series with first term a=1 and common ratio r=79 so has sum a1r=117/9=12/9=92. We can then take E(N) as before.

Comparison to Markov chain solutions

How might I have spotted this from the Markov chain transition matrix? Using @DLDahly's notation, the states in the transition matrix correspond to my description of the number of the number of directions with odd parity.

Spider hunting ant in cube

The one-step transition matrix is

P=[PSSPSAPSBPSEPASPAAPABPAEPBSPBAPBBPBEPESPEAPEBPEE]=[01001/302/3002/301/30001]

The first row show us that after one movement, the spider is guaranteed to be in state A (one odd and two even parities). The two-step transition matrix is:

P(2)=P2=[1/302/3007/902/92/904/91/30001]

The second row shows us that once the spider has entered state A, in two moves time it has either returned to state A with probability 7/9 or has reached state E (all odd parities) and captured the ant, with probabilty 2/9. So having reached state A, we see from the two-step transition matrix that the number of two-step moves required can be analysed using the geometric distribution as above. This isn't how I found my solution, but it is sometimes worth calculating the first few powers of the transition matrix to see if a useful pattern like this can be exploited. I have occasionally found this to give simpler solutions than having to invert a matrix or perform an eigendecomposition by hand - admittedly something that is only really relevant in an exam or interview situation.

Silverfish
fuente
2

He escrito un breve programa Java para responder a su pregunta numéricamente. El recorrido de la araña es verdaderamente aleatorio, lo que significa que también puede atravesar en ciclos antes de llegar a la hormiga.

Sin embargo, no definió el término "esquina opuesta", por lo que tengo dos escenarios diferentes. Enfrente como a través del mismo plano o como a través del cubo. En el primer escenario, la ruta más corta es de 2 pasos y 3 pasos en el segundo escenario.

He usado 100 millones de repeticiones y los resultados son los siguientes:

-- First scenario --
Steps sum: 900019866
Repeats: 100000000
Avg. step count: 9.00019866

-- Second scenario --
Steps sum: 1000000836
Repeats: 100000000
Avg. step count: 10.00000836

Código fuente:

import java.util.Random;
import java.util.concurrent.atomic.AtomicLong;
import java.util.stream.IntStream;

public class ProbabilityQuizSpider {

    // Edges of the cube
    private static final int[][] EDGES = new int[][] {
            {1, 3, 7}, // corner 0
            {0, 2, 4}, // corner 1
            {1, 3, 5}, // corner 2
            {0, 2, 6}, // corner 3
            {1, 5, 7}, // corner 4
            {2, 4, 6}, // corner 5
            {3, 5, 7}, // corner 6
            {0, 4, 6}  // corner 7
    };

    private static final int START = 0; // Spider
    private static final int FINISH = 5; // Ant
    private static final int REPEATS = (int) Math.pow(10, 8);

    public static void main(String[] args) {

        final Random r = new Random();
        final AtomicLong stepsSum = new AtomicLong();

        IntStream.range(0, REPEATS).parallel().forEach(i -> {

            int currentPoint = START;
            int steps = 0;

            do {

                // Randomly traverse to next point
                currentPoint = EDGES[currentPoint][r.nextInt(3)];

                // Increase number of steps
                steps++;

            } while(currentPoint != FINISH);

            stepsSum.addAndGet(steps);

        });

        // Results
        System.out.println("Steps sum: " + stepsSum.get());
        System.out.println("Repeats: " + REPEATS);
        System.out.println("Avg. step count: " + (((double) stepsSum.get()) / ((double) REPEATS)));

    }

}

EDITAR: corrigió un error tipográfico en el script (y también actualizó los resultados)

alesc
fuente
2
I think your edges are wrong. Corner 3 has 7 in its list, but corner 7 doesn't have 3 in its list. (I suggest that the Right Way to map the vertices to the numbers 0..7 is to say that each bit position corresponds to one axis, so that traversing an edge equals XOR with 1, 2, or 4.)
Gareth McCaughan
1
Gracias por su comentario. He hecho un error tipográfico al definir la esquina # 3, debería ser {0, 2, 6}. He vuelto a ejecutar el programa y obtuve el siguiente resultado: 10.00000836 pasos para recorrer desde la esquina # 0 a la esquina # 5 (diagonal del cuerpo del cubo). Esto también es consistente con @Hunaphu.
alesc
Yup, much better.
Gareth McCaughan
2

Resolví tu enigma a través de simulaciones de Monte Carlo (norte=104 4) y obtenido metromiunanorte(stmipagss)10.

Simulación de Monte Carlo ($ n = 10 ^ 4 $)

Aquí está el código R que utilicé:

ant = c(0,0,0) # ant's coordinates 

sim = 1e4 # number of MC simulations
steps = numeric() # initialize array of steps

for (i in 1:sim)
{
  spider = c(1,1,1) # spider's coordinates
  count = 0 # initialize step counter

  # while ant's coordinates == spider's coordinates
  while (!isTRUE(all.equal(ant, spider)))
  {

  # random walk in one of three dimensions
  xyz = trunc(runif(1,1,4))

  # let the spider move
  if (spider[xyz] == 1) 
    {
    spider[xyz] = 0
    } else if (spider[xyz] == 0) 
    {
    spider[xyz] = 1
    }

  # add one step
  count = count + 1
  }

# add the number of step occurred in the ith iteration
steps = c(steps, count)

# print i and number of steps occurred
cat("\n", i, " ::: ", count)
}

# print the mean of steps
(mean(steps))
stochazesthai
fuente
9
El código es agradable y claro, ¡pero les está pidiendo a sus usuarios que vean un millón de líneas impresas en el transcurso de media hora! ¿Y cómo sabes que la respuesta correcta no es, por ejemplo,10.000001? :-) FWIW, puedes explotar algunas Rfunciones nativas para acelerar esto en menos de un segundo:n.sim <- 1e6; x <- matrix(runif(n.sim*3), ncol=3); moves <- x >= pmax(x[, 1], x[, 2], x[, 3]); positions <- apply(moves, 2, cumsum) %% 2; types <- rowSums(positions); vertices <- types[types==0 | types==3]; transitions <- cumsum(diff(vertices) != 0); n.sim / transitions[length(transitions)]
whuber
-1

Creo que alesc está en el camino correcto cuando menciona "Sin embargo, no definió el término" esquina opuesta "A menos que me falte algo en la pregunta, no hay una respuesta correcta, solo respuestas basadas en suposiciones. El tamaño del cubo no está definido IE 10 pies cúbicos, 1000 pies cúbicos, etc. El tamaño de la hormiga no está definido IE pequeño jardín, carpintero, rojo gigante, etc. El tipo de araña no está definido (para determinar el tamaño del escalón) IE pequeño jardín, tarántula, etc. SI combina todo "no definido "variables. la respuesta podría ser 0 pasos o un número indeterminado / infinito de pasos.

RichPT Corona Ca
fuente
3
This answer would not get one to the next level of interviewing unless it were perhaps for a gardening position.
whuber
1
En este caso, es lo suficientemente claro que 'paso' significa 'un movimiento desde un nodo (esquina) a un nodo adyacente', y está bastante claro qué significa "esquina opuesta" de un cubo, por ejemplo, tome un cubo unitario la hormiga está en la esquina (x, y, z) en un cubo unitario, la araña está en (1-x, 1-y, 1-z) (así que si la hormiga está en el origen, la araña está en (1,1 , 1)). Como tal, ninguna de sus preocupaciones parece estar relacionada sustancialmente con la pregunta que se hace. [Nota para los votantes: si bien no creo que esta sea una buena respuesta sin una edición sustancial, no creo que esto deba ser objeto de un voto de supresión, bastan los votos hacia arriba y hacia abajo]
Glen_b -Reinstala a Monica
@Glen_b Since it seems to be seeking clarity on the particulars of the question, I thought this was probably intended as a comment rather than a substantive answer.
Silverfish
1
@Silverfish You may be correct, but then it would close as 'not an answer'. I read it instead as an attempt to say "this question is not answerable", which I'd normally regard as an answer when supported with reasoning, but I think the reasons are simply based on misunderstanding the question.
Glen_b -Reinstate Monica