.. Random Walk .. ============ Random Walk ============ Imagine you are trapped in a maze. It is completely dark, and at every intersection you reach, you randomly choose one of the paths. You also do not memorize any information about the paths or intersections. What is the probability that you will eventually escape the maze? What is the expected time it takes to escape? The general problem of a random walk is as follows: A directed graph is given. For the edges adjacent to each vertex, we have a probability distribution. That is, for each vertex like :math:`v`, and for each of its neighbors like :math:`u`, we define :math:`p_{vu}` as the probability of traversing the edge from :math:`v` to :math:`u`. Additionally, the sum of probabilities for all edges adjacent to :math:`v` must equal 1. Now, we can imagine a person standing on vertex :math:`s`, moving randomly at each step according to the probability distribution of their current vertex. This defines the general framework of the problem. Within this framework, various questions can be asked. Two of the most important questions we will explore in this section are: What is the probability of reaching vertex :math:`t`? And what is the expected number of steps to reach vertex :math:`t`? Converting Problems to Random Walk ---------------------------------- If you pay attention to probability problems, many of them can be converted to Random Walk. This is done by considering a vertex for each possible state (you'll understand more precisely by examining the examples below). The operations we perform are essentially edges that probabilistically change our state (moving us from one vertex to another). We will examine several examples. The Mouse and the Cheese ~~~~~~~~~~~~~~~~~~ Consider an integer number line. A blind mouse is positioned at point :math:`s` and is searching for a piece of cheese located at point :math:`t`. At each step, the mouse moves forward with probability :math:`p` and backward with probability :math:`1-p`. What is the expected number of steps for the mouse to reach the cheese? Conversion ~~~~~~~~~~~ To convert this problem into a random walk, consider a graph with infinitely many vertices where vertex :math:`x` represents the point :math:`x` on the number line. Each vertex :math:`x` has an edge to :math:`x+1` labeled with probability :math:`p`, and an edge to :math:`x-1` labeled with probability :math:`1-p`. The problem now becomes equivalent to finding the expected number of edges traversed to reach from :math:`s` to :math:`t`. Note that we have merely converted this problem into a random walk but have not yet solved it! Bomb ~~~~~~~~~ We have a terrorist holding a button. Every hour, the terrorist presses the button. After pressing the button, the bomb explodes with probability :math:`p` and nothing happens with probability :math:`1-p`. This process continues until the bomb finally explodes (or continues indefinitely). Find the expected time until the bomb explodes. .. code-block:: python :linenos: :emphasize-lines: 3-5,8 :caption: مثالی از یک تابع در پایتون def factorial(n): if n == 0: # agar n sefr bood return 1 else: return n * factorial(n-1) Conversion ~~~~~~~~~~~ Converting this problem into a random walk is not immediately obvious. However, as we mentioned earlier, most probabilistic problems can be transformed into random walks (though the resulting graph doesn't necessarily need to be small, nor does solving the original problem through this random walk conversion need to be simpler). Here, our states are "bomb exploded" and "bomb not exploded". Therefore, it's sufficient to consider two vertices :math:`A` and :math:`B`, where :math:`A` represents the state where the bomb has not exploded. Now, after each hour (each operation), the bomb explodes with probability :math:`p`. Thus, vertex :math:`A` has an edge to :math:`B` labeled with probability :math:`p`. Additionally, with probability :math:`1-p` the bomb doesn't explode, returning us to the previous state - hence vertex :math:`A` has a self-loop edge labeled with probability :math:`1-p`. Ultimately, our problem reduces to finding the expected number of edges needed to transition from :math:`A` to :math:`B`. The discussed graph consequently contains two vertices and two edges! .. image:: images/state_transition.png :align: center :width: 200px :alt: State transition diagram Three Goat-Thief Thieves ~~~~~~~~~~~~~~~~~~~~~~~~ In this problem, we have three goat-thieving thieves whom we will refer to as the first, second, and third. The three thieves are engaged in a game. Each round proceeds as follows: - They randomly select one among themselves. In each step, the first thief has a probability of :math:`\frac 1 2`, the second :math:`\frac 1 3`, and the third :math:`\frac 1 6` of being chosen. Let's call the selected thief Mr. :math:`D`. - Mr. :math:`D` goes to the farm and steals a goat. The stolen goat is added to Mr. :math:`D`'s assets. - If Mr. :math:`D`'s goats now exceed those of one of his friends by at least 2, Mr. :math:`D` becomes the Sultan of Thieves and the game ends. Otherwise, they select another person from among themselves, and the process continues. In general, the thieves repeat this process until a thief who has the highest assets exceeds the thief with the lowest assets by at least two goats... Now, you must calculate the probability that the first thief becomes the Sultan of Thieves! Conversion ~~~~~~~~~~~ The list of different game states is as follows: - All players have equal number of goats. Vertex :math:`s` - First player has one more goat than others. Vertex :math:`A_1` - Second player has one more goat than others. Vertex :math:`B_1` - Third player has one more goat than others. Vertex :math:`C_1` - First player has one fewer goat than others. Vertex :math:`A_{-1}` - Second player has one fewer goat than others. Vertex :math:`B_{-1}` - Third player has one fewer goat than others. Vertex :math:`C_{-1}` - First player becomes sultan. Vertex :math:`A_2` - Second player becomes sultan. Vertex :math:`B_2` - Third player becomes sultan. Vertex :math:`C_3` Each vertex (except the last three) has exactly three outgoing edges depending on which thief is chosen. For example, the adjacent vertices to :math:`A_{-1}` are: - If first is chosen, we go to vertex :math:`s` with probability :math:`\frac 1 2` - If second is chosen, we go to vertex :math:`B_2` with probability :math:`\frac 1 3` - If third is chosen, we go to vertex :math:`C_2` with probability :math:`\frac 1 6` Ultimately, the problem is equivalent to finding the probability of reaching vertex :math:`A_2` from vertex :math:`s`. Solving the Random Walk Problem ---------------------------- In the previous section, we saw that many probability problems can be modeled using Random Walk. However, if this modeling doesn't bring us closer to solving the original problem, it will be of no use to us! In this section, we will see how the probability problem and the expected value of reaching from :math:`s` to :math:`t` in a Random Walk can be solved algorithmically using a system of equations! Assume the probability of moving from vertex :math:`A` to vertex :math:`B` is :math:`P_{AB}`. If there is no edge from :math:`A` to :math:`B` in the graph, consider :math:`P_{AB}=0`. Also, :math:`P_{AB}` is not necessarily equal to :math:`P_{BA}` (since the graph is directed). In this section, we assume vertex :math:`t` is given, and for all vertices like :math:`u`, we want to find the probability and the expected number of edges traversed to reach from :math:`u` to :math:`t`. We denote the probability of reaching from :math:`u` to :math:`t` as :math:`ansP_u`, and the expected number of edges traversed to reach from :math:`u` to :math:`t` as :math:`ansE_u`. Clearly, :math:`ansP_t = 1` and :math:`ansE_t = 0`. The following equations hold for every :math:`u \neq t`: :math:`ansP_u = \sum P_{uv} \times ansP_v` :math:`ansE_u = 1 + \sum P_{uv} \times ansE_v` If we have :math:`n` vertices, these equations give us a system of :math:`n-1` equations with :math:`n-1` unknowns. Additionally, if our directed graph is a DAG, solving the system of equations is unnecessary. Instead, we consider the graph in topological order and compute the solutions from last to first (and this is very similar to what we do in recursive functions). .. code-block:: rst Solving an Example ~~~~~~~~~~~~~~~~~ Here, we aim to solve the bomb problem mentioned earlier. By formulating the system of equations, the result is as follows: :math:`ansE_B = 0` :math:`ansE_A = 1 + (1-p) \times ansE_A + p \times ansE_B` which easily yields :math:`ansE_A = \frac 1 p` Conclusion -------------- Here, we entered the space of Random Walks and briefly discussed some problems defined in this space. However, the truth is that the variety of questions raised in the Random Walk domain is vast, and a detailed discussion would be beyond the scope of this book. The method we described for converting to a Random Walk and solving it is very general. This approach is good for building our intuition about problems, but often the constructed graph becomes too large to solve its equations manually (like the *three thieves problem*). Sometimes, we can leverage the graph's specific properties. For example, suppose we want to find the expected number of steps to reach vertex :math:`t` from :math:`s`, and the graph's structure is such that every path from :math:`s` to :math:`t` necessarily passes through vertex :math:`w`. According to the laws of expectation, we can conclude that the expected number of edges to reach from :math:`s` to :math:`t` equals the sum of the expected steps from :math:`s` to :math:`w` and then from :math:`w` to :math:`t`. You can use this idea to solve the *Mouse and Cheese problem*! In summary, converting problems into Random Walks can be helpful, but often it is not sufficient on its own. We must employ more creativity to simplify the problem further.