{
  "format": "srwb",
  "version": "1.0",
  "notebook": {
    "name": "Markov Groups: A Random Walk on Cube Moves",
    "cells": [
      {
        "name": "intro",
        "type": "markdown",
        "language": "markdown",
        "code": "# Markov Groups: A Random Walk on Cube Moves\n\nThis lesson separates three ideas:\n\n1. A legal cube move is a **permutation** of sticker positions.\n2. Repeating one quarter turn gives powers with exponent **modulo 4**.\n3. Choosing legal moves at random creates a **Markov chain** on reachable cube states.\n\nWe use a standard 3×3×3 Rubik's Cube with 54 labelled stickers. Labels `1..54` identify individual stickers, not just colours. All six face centres stay fixed. A quarter turn is clockwise when you look directly at the outside of the turned face; see [Rubik's official move guide](https://rubiks.com/solve-guide).\n\n## Runtime and run order\n\nRun the Python cells in order: `cube_moves`, `check_moves`, `show_turn`, then `random_walk`. They share the Python session. NumPy is the only package used and SciREPL loads it with its Pyodide runtime; first use may need a runtime download. No AI account, prompt execution, extra package installation, or external data is needed. This catalog copy has no saved outputs.\n\nBefore running `check_moves`, predict: which stickers must never change position, and how many repeated quarter turns should restore every label?"
      },
      {
        "name": "coordinates",
        "type": "markdown",
        "language": "markdown",
        "code": "## Stage 1 — fix the layout and matrix convention\n\nFace order is **U, D, F, B, L, R** (up, down, front, back, left, right). Each face occupies nine consecutive **zero-based positions**, read row-major while looking at that face from outside:\n\n```\n0 1 2\n3 4 5\n6 7 8\n```\n\nAdd `9 * face_index` for a particular face. The centre positions are `4, 13, 22, 31, 40, 49`. Sticker labels are one-based, so the label initially at position `j` is `j + 1`.\n\nTo remove orientation ambiguity, use coordinates x = right, y = up, z = front. In the table, “right” and “up” are directions in the face's outside-view drawing.\n\n| Face | Outward normal | Drawing right | Drawing up |\n| --- | --- | --- | --- |\n| U | (0, 1, 0) | (1, 0, 0) | (0, 0, -1) |\n| D | (0, -1, 0) | (1, 0, 0) | (0, 0, 1) |\n| F | (0, 0, 1) | (1, 0, 0) | (0, 1, 0) |\n| B | (0, 0, -1) | (-1, 0, 0) | (0, 1, 0) |\n| L | (-1, 0, 0) | (0, 0, 1) | (0, 1, 0) |\n| R | (1, 0, 0) | (0, 0, -1) | (0, 1, 0) |\n\nA permutation `p` maps a **source position** `j` to its **destination** `p[j]`. For a column state vector `s`, set `P[p[j], j] = 1`. Then `s_next = P @ s`, equivalently `s_next[p[j]] = s[j]`. Rows are destinations; columns are sources. The next cell uses disjoint cycles, each written in source-to-destination order."
      },
      {
        "name": "cube_moves",
        "type": "code",
        "language": "python",
        "code": "import numpy as np\n\nN = 54\nFACE_NAMES = \"UDFBLR\"\nCENTRES = np.array([9 * f + 4 for f in range(6)])\n\n# Five disjoint 4-cycles per clockwise face turn: two on the face,\n# three on the surrounding strips. Indices are zero-based positions.\nMOVE_CYCLES = {\n    \"U\": [\n        [\n            0,\n            2,\n            8,\n            6\n        ],\n        [\n            1,\n            5,\n            7,\n            3\n        ],\n        [\n            18,\n            36,\n            27,\n            45\n        ],\n        [\n            19,\n            37,\n            28,\n            46\n        ],\n        [\n            20,\n            38,\n            29,\n            47\n        ]\n    ],\n    \"D\": [\n        [\n            9,\n            11,\n            17,\n            15\n        ],\n        [\n            10,\n            14,\n            16,\n            12\n        ],\n        [\n            24,\n            51,\n            33,\n            42\n        ],\n        [\n            25,\n            52,\n            34,\n            43\n        ],\n        [\n            26,\n            53,\n            35,\n            44\n        ]\n    ],\n    \"F\": [\n        [\n            6,\n            45,\n            11,\n            44\n        ],\n        [\n            7,\n            48,\n            10,\n            41\n        ],\n        [\n            8,\n            51,\n            9,\n            38\n        ],\n        [\n            18,\n            20,\n            26,\n            24\n        ],\n        [\n            19,\n            23,\n            25,\n            21\n        ]\n    ],\n    \"B\": [\n        [\n            0,\n            42,\n            17,\n            47\n        ],\n        [\n            1,\n            39,\n            16,\n            50\n        ],\n        [\n            2,\n            36,\n            15,\n            53\n        ],\n        [\n            27,\n            29,\n            35,\n            33\n        ],\n        [\n            28,\n            32,\n            34,\n            30\n        ]\n    ],\n    \"L\": [\n        [\n            0,\n            18,\n            9,\n            35\n        ],\n        [\n            3,\n            21,\n            12,\n            32\n        ],\n        [\n            6,\n            24,\n            15,\n            29\n        ],\n        [\n            36,\n            38,\n            44,\n            42\n        ],\n        [\n            37,\n            41,\n            43,\n            39\n        ]\n    ],\n    \"R\": [\n        [\n            2,\n            33,\n            11,\n            20\n        ],\n        [\n            5,\n            30,\n            14,\n            23\n        ],\n        [\n            8,\n            27,\n            17,\n            26\n        ],\n        [\n            45,\n            47,\n            53,\n            51\n        ],\n        [\n            46,\n            50,\n            52,\n            48\n        ]\n    ]\n}\n\ndef turn_perm(name):\n    \"\"\"Return p: source position j moves to destination p[j].\"\"\"\n    p = np.arange(N)\n    for cycle in MOVE_CYCLES[name]:\n        for source, destination in zip(cycle, cycle[1:] + cycle[:1]):\n            p[source] = destination\n    return p\n\ndef perm_matrix(p):\n    \"\"\"Rows are destinations, columns are sources.\"\"\"\n    p = np.asarray(p)\n    if p.shape != (N,) or not np.array_equal(np.sort(p), np.arange(N)):\n        raise ValueError(\"Expected a permutation of positions 0..53\")\n    P = np.zeros((N, N), dtype=int)\n    P[p, np.arange(N)] = 1\n    return P\n\nPERMS = {name: turn_perm(name) for name in FACE_NAMES}\nM = {name: perm_matrix(PERMS[name]) for name in FACE_NAMES}\nIDENTITY = np.eye(N, dtype=int)\nSOLVED = np.arange(1, N + 1)\n\ndef sticker_state(state):\n    values = np.asarray(state)\n    if values.shape != (N,) or not np.array_equal(np.sort(values), SOLVED):\n        raise ValueError(\"Expected each sticker label 1..54 exactly once\")\n    return values.astype(int, copy=True)\n\ndef apply(state, *moves):\n    \"\"\"Apply moves left to right; an apostrophe means the inverse.\"\"\"\n    result = sticker_state(state)\n    for move in moves:\n        if move == \"I\":\n            continue\n        if move in M:\n            matrix = M[move]\n        elif move.endswith(\"'\") and move[:-1] in M:\n            matrix = M[move[:-1]].T\n        else:\n            raise ValueError(\"Unknown move: \" + move)\n        result = matrix @ result\n    return result\n\ndef stickers_to_colours(state):\n    \"\"\"Return home-face letters as colour labels, not physical paint names.\"\"\"\n    return [FACE_NAMES[(int(label) - 1) // 9] for label in sticker_state(state)]\n\nprint(\"Built six clockwise quarter-turn matrices with fixed face centres.\")"
      },
      {
        "name": "check_moves",
        "type": "code",
        "language": "python",
        "code": "# Stage 2: verify properties that colours alone cannot reveal.\nfor name in FACE_NAMES:\n    p, matrix = PERMS[name], M[name]\n    assert np.array_equal(np.sort(p), np.arange(N)), name + \": not bijective\"\n    assert np.array_equal(p[CENTRES], CENTRES), name + \": centre moved\"\n    assert np.all(matrix.sum(axis=0) == 1), name + \": bad source column\"\n    assert np.all(matrix.sum(axis=1) == 1), name + \": bad destination row\"\n    assert np.array_equal(np.linalg.matrix_power(matrix, 4), IDENTITY), name + \": fourth power is not identity\"\n    assert np.array_equal(matrix.T @ matrix, IDENTITY), name + \": inverse failed\"\n    assert np.array_equal(apply(SOLVED, name, name, name, name), SOLVED)\n    assert np.array_equal(apply(SOLVED, name, name + \"'\"), SOLVED)\n    print(name + \": bijection, fixed centres, four turns, and inverse passed\")\n\nassert not np.array_equal(M[\"U\"] @ M[\"R\"], M[\"R\"] @ M[\"U\"])\nprint(\"All six moves passed. U and R do not commute.\")"
      },
      {
        "name": "cycles",
        "type": "markdown",
        "language": "markdown",
        "code": "## Stage 3 — circles, cycles, and modular arithmetic\n\nEvery face turn contains five disjoint **4-cycles**. For example, its face corners make one 4-cycle and its four non-corner edge stickers make another. The centre is fixed.\n\nDraw one listed cycle as four positions around a circle. One quarter turn advances one step; two turns advance two steps; four turns return to the start. For a fixed move `P`, `P^k = P^(k mod 4)`. Its inverse is `P^3 = P.T`, and a half turn is `P^2`.\n\nThis is a cyclic subgroup of order 4. It does **not** make the entire cube group modular arithmetic: different face turns need not commute. With column vectors, “U, then R” is `M[\"R\"] @ M[\"U\"] @ s`, not the reverse matrix product. In the next cell, compare the same two moves in opposite orders."
      },
      {
        "name": "show_turn",
        "type": "code",
        "language": "python",
        "code": "after_u = apply(SOLVED, \"U\")\nprint(\"U cycles, shown as one-based sticker positions:\")\nfor cycle in MOVE_CYCLES[\"U\"]:\n    print(\" -> \".join(str(position + 1) for position in cycle + cycle[:1]))\n\n# F is face index 2, so its top row is at positions 18, 19, 20.\nfront_top = np.arange(18, 21)\nprint(\"\\nF top row labels before U:\", SOLVED[front_top].tolist())\nprint(\"F top row labels after U: \", after_u[front_top].tolist())\nprint(\"Face-letter colours after U:\", stickers_to_colours(after_u))\nprint(\"U then R equals R then U:\",\n      np.array_equal(apply(SOLVED, \"U\", \"R\"), apply(SOLVED, \"R\", \"U\")))\nassert not np.array_equal(apply(SOLVED, \"U\", \"R\"), apply(SOLVED, \"R\", \"U\"))"
      },
      {
        "name": "markov_bridge",
        "type": "markdown",
        "language": "markdown",
        "code": "## Stage 4 — choose a move at random\n\nA Markov chain specifies probabilities for the next state using only the current state. Choose uniformly among **13 options**: stay still (`I`), the six quarter turns, and their six inverses. Apply the chosen move to the current cube state.\n\nBecause inverse moves have the same probability, the walk is symmetric. Staying still makes it lazy, avoiding the parity alternation of a walk made only of quarter turns. On the finite set of cube states reachable by these generators, the uniform distribution is stationary; reachability and the self-loop give irreducibility and aperiodicity. This does **not** say that a short random sequence is uniformly mixed, or establish a mixing time.\n\nThe average `T = (I + sum(P + P.T)) / 13` is also useful, but it is only a **54×54 one-sticker location model**, not the transition matrix for all cube configurations. With column probability vectors, columns of `T` sum to 1 and `x_next = T @ x`. Here `T` is symmetric, so its rows sum to 1 as well. A centre sticker stays at its own position; not every sticker can visit every position.\n\nA stochastic average is not a legal deterministic cube move: averaging label vectors can produce fractional labels. Apply an actual chosen permutation to obtain a cube state; use `T` only for a probability distribution."
      },
      {
        "name": "random_walk",
        "type": "code",
        "language": "python",
        "code": "MOVE_OPTIONS = [\"I\", \"U\", \"U'\", \"D\", \"D'\", \"F\", \"F'\", \"B\", \"B'\", \"L\", \"L'\", \"R\", \"R'\"]\nT = (IDENTITY + sum((M[name] + M[name].T for name in FACE_NAMES), np.zeros((N, N), dtype=int))) / len(MOVE_OPTIONS)\nassert np.all(T >= 0)\nassert np.allclose(T.sum(axis=0), 1)\nassert np.allclose(T.sum(axis=1), 1)\nassert np.allclose(T, T.T)\n\n# A distribution for the location of one particular sticker.\nlocation_probability = np.zeros(N)\nlocation_probability[0] = 1\nafter_one_step = T @ location_probability\nassert np.isclose(after_one_step.sum(), 1)\nprint(\"One-sticker probability mass after one step:\", round(float(after_one_step.sum()), 6))\n\n# Sample a valid cube trajectory. The seed makes this example reproducible,\n# not uniformly mixed over all reachable cube configurations.\nrng = np.random.default_rng(7)\nmoves = rng.choice(MOVE_OPTIONS, size=12).tolist()\nwalk_state = apply(SOLVED, *moves)\nassert np.array_equal(np.sort(walk_state), SOLVED)\nassert np.array_equal(walk_state[CENTRES], SOLVED[CENTRES])\nprint(\"Sampled moves:\", \" \".join(moves))\nprint(\"Final face-letter colours:\", stickers_to_colours(walk_state))\nprint(\"The sampled path preserved every sticker label and all six centres.\")"
      },
      {
        "name": "takeaways",
        "type": "markdown",
        "language": "markdown",
        "code": "## Check your understanding\n\n1. Why does checking only colours fail to reveal some incorrect permutations within a face?\n2. Why must a quarter turn fix the centre and satisfy `P^4 = I`?\n3. Why is the matrix product for “U, then R” written in reverse chronological order?\n4. Why does modulo 4 describe powers of one face turn, but not arbitrary sequences of different face turns?\n5. What does the 54×54 stochastic matrix describe? Why is it not the full cube-state Markov chain?\n6. Why does a reproducible 12-step random walk not prove uniform scrambling?\n\nThe full cube group is generated by the six face moves, with inverse moves already obtainable as third powers. We do not claim that U, R, and F alone generate the full group: all three leave the opposite D–B–L corner untouched.\n\n**Main lesson:** distinguish a legal permutation, its cyclic powers, and a probability mixture of moves. Those are connected ideas, not interchangeable objects."
      }
    ]
  }
}