Losowy spacer po krawędziach sześcianu

Mrówka jest umieszczana w rogu sześcianu i nie może się poruszać. Pająk zaczyna od przeciwnego rogu i może poruszać się wzdłuż krawędzi sześcianu w dowolnym kierunku z jednakowym prawdopodobieństwem . Średnio ile kroków będzie musiał pająk dostać się do mrówki?$(x,y,z)$$1/3$

(To nie jest praca domowa, to pytanie do wywiadu.)

Sugeruję modelowanie problemu jako łańcuch Markowa, w którym każdy stan reprezentuje odległość między pająkiem a mrówką. W tym przypadku mamy 4 możliwe stany ponieważ odległości mogą wynosić .$S_i$$i$$\{0,1,2,3\}$

Kiedy pająk znajduje się w przeciwległym rogu sześcianu, znajduje się w odległości 3 kroków od mrówki. Jest w stanie .$S_3$

Budowanie macierzy przejścia .$\mathbf{P}$

• Jeśli narysujemy sześcian, zobaczymy, że gdy jesteśmy w stanie , każdy ruch zmniejsza odległość między pająkiem a mrówką do 2 kroków. Tak więc, gdy jesteśmy w stanie , przechodzimy do stanu z prawdopodobieństwem 1.$S_3$$S_3$$S_2$

• Kiedy jesteśmy w stanie , możemy wrócić do stanu używając krawędzi, którą stamtąd przybyliśmy, lub możemy zmniejszyć odległość do tylko jednego kroku, jeśli wybieramy dwie inne krawędzie. Tak więc, gdy jesteśmy w stanie , możemy przejść do stanu z prawdopodobieństwem 2/3 i do stanu z prawdopodobieństwem 1/3.$S_2$$S_3$$S_2$$S_1$$S_3$

• Gdy jesteśmy w stanie , możemy przejść do stanu używając jednej z trzech możliwych krawędzi. Jeśli użyjemy pozostałych dwóch, wrócimy do stanu . Tak więc, gdy jesteśmy w stanie , możemy przejść do stanu z prawdopodobieństwem 1/3 i do stanu z prawdopodobieństwem 2/3.$S_1$$S_0$$S_2$$S_1$$S_0$$S_2$

• Kiedy dochodzimy do stanu , zostajemy tam, ponieważ jest to naszym celem. jest stanem pochłaniającym.$S_0$$S_0$

$$\begin{equation} \mathbf{P} = \left[\begin{array}{cccc} P_{S_3 \to S_3} & P_{S_3 \to S_2}& P_{S_3 \to S_1} & P_{S_3 \to S_0} \\ P_{S_2 \to S_3} & P_{S_2 \to S_2}& P_{S_2 \to S_1} & P_{S_2 \to S_0} \\ P_{S_1 \to S_3} & P_{S_1 \to S_2}& P_{S_1 \to S_1} & P_{S_1 \to S_0} \\ P_{S_0 \to S_3} & P_{S_0 \to S_2} & P_{S_0 \to S_1}& P_{S_0 \to S_0} \\ \end{array}\right] = \left[\begin{array}{cccc} 0 & 1 & 0 & 0 \\ 1/3 & 0 & 2/3 & 0 \\ 0 & 2/3 & 0 & 1/3 \\ 0 & 0 & 0 & 1 \\ \end{array}\right] \end{equation}$$

Jest to pochłaniający łańcuch Markowa z trzema stanami przejściowymi ( , S 2 , S 1 ) i jednym stanem pochłaniającym ( S 0 ).$S_3$$S_2$$S_1$$S_0$

Zgodnie z teorią macierz przejściowa łańcucha Markowa z stanami przejściowymi i stanami pochłaniania r może zostać przepisana jako: P = [ Q t R 0 r × t I r$t$$r$

$$\begin{equation} \mathbf{P} = \left[\begin{array}{cc} \mathbf{Q}_t &\mathbf{R} \\ \mathbf{0}_{r \times t} & \mathbf{I}_r \\ \end{array}\right] \end{equation}$$

gdzie jest w odległości t x t matrycy, który pokazuje prawdopodobieństwo przejście z pewnym stanie nieustalonym do innego stanie nieustalonym, a R jest t x R macierz prawdopodobieństw przejście z jednego z T stanów przejściowych z jednym z r absorbujący stany. Macierz tożsamości I r pokazuje nam, że gdy osiągnięty zostanie którykolwiek ze stanów pochłaniania r , nie następuje przejście od tego stanu. Macierz wszystkich zer 0 r × t można interpretować jako brak przejścia z któregokolwiek z $\mathbf{Q}_t$$t \times t$$\mathbf{R}$$t \times r$$t$$r$$\mathbf{I}_r$$r$$\mathbf{0}_{r \times t}$$r$stany pochłaniające do dowolnego z stanów przejściowych.$t$

wejścia Q , T oznacza prawdopodobieństwo przejścia ze stanu ı do stanu j dokładnie w jednym etapie. Aby uzyskać prawdopodobieństwo dla k kroków, potrzebujemy wpisu ( i , j ) Q k t . Podsumowując dla wszystkich k , otrzymujemy macierz, która zawiera w swoim ( i , j ) wpisie oczekiwaną liczbę wizyt w stanie przejściowym j po rozpoczęciu od stanu przejściowego i .$(i,j)$$\mathbf{Q}_t$$i$$j$$k$$(i,j)$$\mathbf{Q}_t^k$$k$$(i,j)$$j$$i$

$$\begin{equation} \sum_{k=0}^{\infty} \mathbf{Q}_t^k = (\mathbf{I}_t - \mathbf{Q}_t)^{-1} \end{equation}$$

Aby uzyskać liczbę kroków do wchłonięcia, po prostu zsumuj wartości każdego rzędu . Może to być reprezentowane przez$(\mathbf{I}_t - \mathbf{Q}_t)^{-1}$

$$\begin{equation} \mathbf{t} = (\mathbf{I}_t - \mathbf{Q}_t)^{-1} \mathbf{1} \end{equation}$$

gdzie jest wektorem kolumny ze wszystkimi składnikami równymi 1.$\mathbf{1}$

Zastosujmy to do naszego przypadku:

Jak wspomniano powyżej, w tym przypadku mamy = 3 stanów przejściowych i r = 1 stan chłonnej, więc: Q , T = [ 0 1 0 1 / 3 0 2 / 3 0 2 / 3 0$t$$r$

$$\begin{equation} \mathbf{Q}_t = \left[\begin{array}{ccc} 0 & 1 & 0 \\ 1/3 & 0 & 2/3\\ 0 & 2/3 & 0 \\ \end{array}\right] \quad \quad \mathbf{R} = \left[\begin{array}{c} 0 \\ 0\\ 1/3 \\ \end{array}\right] \end{equation}$$

Macierz z oczekiwaną liczbą odwiedzin wynosi

$$\begin{equation} (\mathbf{I}_t - \mathbf{Q}_t)^{-1} = \left[\begin{array}{ccc} 2.5 & 4.5 & 3 \\ 1.5 & 4.5 & 3\\ 1 & 3 & 3 \\ \end{array}\right] \end{equation}$$

Matrycę tę można interpretować w następujący sposób. Zaczynając od stanu a przed wchłonięciem w S 0 odwiedzamy średnio S 3 2,5 razy, S 2 4,5 razy i S 13 razy.$S_3$$S_0$$S_3$$S_2$$S_1$

Oczekiwana liczba kroków od stanu do stanu S 0 jest określona przez pierwszy składnik następującego wektora:$S_3$$S_0$

$$\begin{equation} \mathbf{t} = \left[\begin{array}{ccc} 2.5 & 4.5 & 3 \\ 1.5 & 4.5 & 3\\ 1 & 3 & 3 \\ \end{array}\right] \left[\begin{array}{c} 1 \\ 1\\ 1\\ \end{array}\right] = \left[\begin{array}{c} 10 \\ 9\\ 7\\ \end{array}\right]. \end{equation}$$

Drugi i trzeci składnik to oczekiwana liczba kroków do S 0, jeśli zaczniemy odpowiednio od S 2 i S 1 .$\mathbf{t}$$S_0$$S_2$$S_1$

Let $x^*$ be the number of expected steps. Let $x_1$ be the number of expected steps from any corner adjacent to the origin of the spider and $x_0$ ditto for the ant.

Then $x^* = 1 + x_1$ and $x_0 = 1 + \frac{2}{3}x_1$. Since

$$x_1 = 1 + \frac{2}{3}x_0 + \frac{1}{3}x^*= 1 + \frac{2}{3}x_0 + \frac{1}{3} + \frac{1}{3}x_1$$

we get that $x_1 = x_0 + 2$. So $x_0 = 1 + \frac{2}{3}x_0 + \frac{4}{3}$ implying that $x_0=7$ and $x_1=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 $x_1$. From $x_1$, 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 $x_0$. From these positions we can reach the goal in one step with probability $1/3$ or go back to one of the $x_1$-positions with probability $2/3$. This means that $x_0 = \frac{1}{3}1 + \frac{2}{3}(1 + x_1) = 1 + \frac{2}{3}x_1$.

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 $1\to0$ or $0\to1$. 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:

$$\mathbb E(\mathrm{steps}) = \sum_{n=0}^{\infty} (3 + 2n) \cdot \frac{2}{9} \cdot \left ( \frac{7}{9} \right ) ^{n} = 10$$

Just to compliment tiagotvv's answer:

Naturalnie nie myślę o tego rodzaju problemach jako o matrycach (nawet jeśli są). Muszę to wyciągnąć, co zrobiłem poniżej. Widać, że istnieją 3 miejsca do przejścia z S, z których wszystkie są As. Z dowolnego A możesz wrócić do S lub przejść do jednego z dwóch Bs. Z dowolnego B możesz przejść do E lub do jednego z dwóch As. Wszystko to przekłada się na macierz przejścia podaną przez tiagotvv, którą można również narysować w formie wykresu.

Ponieważ jestem okropny z matematyki, po prostu spróbuję zasymulować twój problem. Możesz to zrobić za pomocą pakietu markovchain w 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())

  # 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

Odpowiedź tiagotvv można obliczyć w R jako:

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

Względy parzystości dają bardzo czyste rozwiązanie, przy użyciu zaskakująco prostych mechanizmów: bez łańcuchów Markowa, bez powtarzanych oczekiwań i tylko podsumowania na poziomie szkoły średniej. Podstawową ideą jest to, że jeśli pająk poruszył się parzystą liczbę razy w$x$ kierunek, powrócił do swojego pierwotnego $x$współrzędna, więc nie może być w pozycji mrówki. Jeśli poruszył się nieparzystą liczbę razy w$x$ kierunek, to jego $x$współrzędna odpowiada mrówce. Tylko jeśli poruszył się nieparzystą liczbę razy we wszystkich trzech kierunkach, będzie pasował do$x$, $y$ i $z$ współrzędne mrówki.

Początkowo pająk wykonał zero ruchów w dowolnym z trzech kierunków, więc parzystość dla każdego kierunku jest parzysta. Wszystkie trzy parytety muszą zostać odwrócone, aby dotrzeć do mrówki.

Po pierwszym ruchu pająka (oznaczmy ten kierunek $x$), dokładnie jeden kierunek ma nieparzystą parzystość, a pozostałe dwa ($y$ i $z$) są parzyste. Aby złapać mrówkę, tylko te dwa parytety muszą zostać odwrócone. Ponieważ nie można tego osiągnąć w nieparzystej liczbie kolejnych ruchów, odtąd rozważamy pary ruchów. Istnieje dziewięć możliwych kombinacji dla pierwszego sparowanego ruchu:

$$(x,x), \,(x,y), \,(x,z), \,(y,x), \,(y,y), \,(y,z), \,(z,x), \,(z,y), \text{or} \,(z,z)$$

Musimy się wprowadzić $y$ i $z$ wskazówki, jak dotrzeć do mrówki po jednym sparowanym ruchu, a osiągną to dwie z dziewięciu kombinacji: $(y,z)$ i $(z,y)$ zapewniłby, że wszystkie trzy parytety są nieparzyste.

Pozostałe siedem kombinacji pozostawia jeden parzysty i dwa parzyste. Trzy powtarzające się ruchy$(x,x)$, $(y,y)$ lub $(z,z)$, pozostaw wszystkie parytety na niezmienionym poziomie, więc nadal potrzebujemy jednego $y$ i jeden $z$ruch do mrówki. Pozostałe pary zawierają dwa różne ruchy, w tym jeden w$x$kierunek. To przełącza parzystość$x$ i jeden z pozostałych parytetów (albo $y$ lub $z$), więc nadal mamy jeden parzysty nieparzysty i dwa parzyste. Na przykład para$(x,z)$ pozostawia nas potrzebujących jeszcze jednego $x$ i jeszcze jeden $y$dotrzeć do mrówki: sytuacja równoważna (po ponownym znakowaniu osi) do poprzedniej. Następnie możemy przeanalizować następny sparowany ruch w ten sam sposób.

In general paired moves start with one odd and two even parities, and will either end with three odd parities (with probability $\frac{2}{9}$) and the immediate capture of the ant, or with one odd and two even parities (with probability $\frac{7}{9}$) 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, \dots\}$ with probability of success $p = \frac{2}{9}$ so has mean $\mathbb{E}(M) = p^{-1} = \frac{9}{2} = 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$ stosując liniowość oczekiwań, $\mathbb{E}(N) = 2\mathbb{E}(M) + 1 = 2 \times 4.5 + 1 = 10$.

Możesz też zauważyć $P(M \geq m) = (\frac{7}{9})^{m-1}$i zastosuj dobrze znaną formułę dla średniej dyskretnego rozkładu przyjmującego tylko nieujemne wartości całkowite ,$\mathbb{E}(M)=\sum_{m=1}^\infty P(M\geq m)$. To daje$\mathbb{E}(M)=\sum_{m=1}^\infty (\frac{7}{9})^{m-1}$ który jest serią geometryczną z pierwszym terminem $a=1$ i wspólny stosunek $r=\frac{7}{9}$ ma też sumę $\frac{a}{1-r} = \frac{1}{1-7/9}=\frac{1}{2/9}=\frac{9}{2}$. Możemy wtedy wziąć$\mathbb{E}(N)$ jak wcześniej.

Porównanie do rozwiązań łańcuchowych Markowa

Jak mogłem to zauważyć w macierzy przejścia łańcucha Markowa? Używając notacji @ DLDahly, stany w macierzy przejścia odpowiadają mojemu opisowi liczby kierunków z nieparzystą parzystością.

Macierz przejścia jednoetapowego to

$$\begin{equation} \mathbf{P} = \left[\begin{array}{cccc} P_{S \to S} & P_{S \to A}& P_{S \to B} & P_{S \to E} \\ P_{A \to S} & P_{A \to A}& P_{A \to B} & P_{A \to E} \\ P_{B \to S} & P_{B \to A}& P_{B \to B} & P_{B \to E} \\ P_{E \to S} & P_{E \to A} & P_{E \to B}& P_{E \to E} \\ \end{array}\right] = \left[\begin{array}{cccc} 0 & 1 & 0 & 0 \\ 1/3 & 0 & 2/3 & 0 \\ 0 & 2/3 & 0 & 1/3 \\ 0 & 0 & 0 & 1 \\ \end{array}\right] \end{equation}$$

Pierwszy rząd pokazuje nam, że po jednym ruchu pająk jest w stanie A (jeden nieparzysty i dwa parzyste). Dwuetapowa macierz przejścia to:

$$\begin{equation} \mathbf{P}^{(2)} = \mathbf{P}^{2} = \left[\begin{array}{cccc} 1/3 & 0 & 2/3 & 0 \\ 0 & 7/9 & 0 & 2/9 \\ 2/9 & 0 & 4/9 & 1/3 \\ 0 & 0 & 0 & 1 \\ \end{array}\right] \end{equation}$$

Drugi rząd pokazuje nam, że po wejściu pająka w stan A, w czasie dwóch ruchów albo z prawdopodobieństwem powrócił do stanu A $7/9$ lub osiągnął stan E (wszystkie nieparzyste parytety) i schwytał mrówkę z prawdopodobieństwem $2/9$. Po osiągnięciu stanu A widzimy z dwuetapowej macierzy przejścia, że ​​liczbę wymaganych ruchów dwuetapowych można analizować przy użyciu rozkładu geometrycznego jak powyżej. Nie tak znalazłem swoje rozwiązanie, ale czasami warto obliczyć kilka pierwszych mocy macierzy przejścia, aby sprawdzić, czy można wykorzystać taki użyteczny wzór. Czasami zdarza mi się, że daje to prostsze rozwiązania, niż konieczność odwracania matrycy lub ręcznego wykonywania eigendecompozycji - co prawda jest tak naprawdę istotne tylko w przypadku egzaminu lub rozmowy kwalifikacyjnej.

Napisałem krótki program Java, aby liczbowo odpowiedzieć na twoje pytanie. Przemieszczanie się pająka jest naprawdę losowe, co oznacza, że ​​może również przemieszczać się cyklicznie przed dotarciem do mrówki.

Nie zdefiniowałeś jednak terminu „przeciwny róg”, więc mam dwa różne scenariusze. Naprzeciwko jak w poprzek tej samej płaszczyzny lub jak przez sześcian. W pierwszym scenariuszu najkrótsza ścieżka to 2 kroki i 3 kroki w drugim scenariuszu.

Użyłem 100 milionów powtórzeń, a wyniki są następujące:

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

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

Kod źródłowy:

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)));

    }

}

EDYCJA: poprawiono literówkę w skrypcie (a także zaktualizowałem wyniki)

Rozwiązałem waszą zagadkę za pomocą symulacji Monte Carlo ($n = 10^4$) i uzyskane $\mathtt{mean(steps)} \approx 10$.

Oto kod R, którego użyłem:

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))

Uważam, że alesc jest na dobrej drodze, gdy wspomina „Jednak nie zdefiniowałeś terminu„ przeciwny róg ”. O ile nie brakuje mi czegoś w pytaniu, nie ma poprawnej odpowiedzi, tylko odpowiedzi oparte na założeniach. Rozmiar kostki nie jest zdefiniowany IE 10 stóp sześciennych, 1000 stóp sześciennych itp. Rozmiar mrówki nie jest zdefiniowany IE mały ogród, cieśla, olbrzymi czerwony itp., Typ pająka nie jest zdefiniowany (aby określić rozmiar kroku) IE mały ogród, tarantula itp. JEŻELI połączysz wszystkie „nie zdefiniowano "zmienne. Odpowiedź może wynosić 0 kroków lub nieokreśloną / nieskończoną liczbę kroków.