Skip to content

plurigrid/asi / ies/music-topos/.codex/skills/spectral-random-walker

spectral-random-walker

Verified

FileKindSize
SKILL.mdskill md2.8 KB
spectral_random_walk.jlother10.9 KB

spectral_random_walk.jl

View on GitHub
"""
    spectral_random_walk.jl

Spectral Random Walk Analysis for Proof Dependency Graphs
===========================================================

Integration of spectral architecture with random walk theory on graphs.

Key insight (Benjamin Merlin Bumpus): The spectral gap λ₁ - λ₂ of a graph's
Laplacian controls the mixing time of random walks.

Mixing time ∝ 1 / (spectral gap)

Lower gap → slower mixing → more tangled dependencies
Higher gap → faster mixing → optimal connectivity (Ramanujan)

This module enables:
  1. Random walk simulation on proof dependency graphs
  2. Mixing time estimation from spectral gap
  3. Path sampling via Metropolis-Hastings
  4. Comprehension-based theorem discovery
"""

using LinearAlgebra
using Statistics
using Random

module SpectralRandomWalk

import LinearAlgebra: eigvals, Symmetric, Diagonal
import Statistics: quantile, mean

export RandomWalkAnalysis, simulate_random_walk, estimate_mixing_time
export sample_proof_paths, comprehension_discovery

# ============================================================================
# Part 1: Random Walk on Spectral Graphs
# ============================================================================

"""
    RandomWalkAnalysis

Records a random walk trajectory on a graph.
"""
struct RandomWalkAnalysis
    start_node::Int
    current_node::Int
    visited_path::Vector{Int}
    visit_counts::Dict{Int, Int}
    transition_count::Int
    stationary_approximation::Dict{Int, Float64}
end

"""
    estimate_mixing_time(spectral_gap::Float64, num_nodes::Int) -> Float64

Estimate random walk mixing time from spectral gap.

Theory: mixing_time ≈ log(num_nodes) / spectral_gap

Args:
  - spectral_gap: λ₁ - λ₂
  - num_nodes: Number of nodes in graph

Returns:
  - Estimated mixing time (number of steps)
"""
function estimate_mixing_time(spectral_gap::Float64, num_nodes::Int)
    if spectral_gap <= 0.0
        return Inf
    end
    return log(Float64(num_nodes)) / spectral_gap
end

"""
    simulate_random_walk(adjacency::Matrix, start::Int, num_steps::Int) -> RandomWalkAnalysis

Simulate random walk on graph via uniform neighbor selection.

Args:
  - adjacency: Adjacency matrix (symmetric, undirected)
  - start: Starting node (1-indexed)
  - num_steps: Number of steps to take

Returns:
  - RandomWalkAnalysis with path and statistics
"""
function simulate_random_walk(adjacency::Matrix, start::Int, num_steps::Int)
    n = size(adjacency, 1)
    
    # Normalize adjacency to transition matrix
    degrees = vec(sum(adjacency, dims=2))
    P = zeros(Float64, n, n)
    
    for i in 1:n
        if degrees[i] > 0
            P[i, :] = adjacency[i, :] / degrees[i]
        end
    end
    
    # Simulate walk
    current = start
    path = [current]
    visit_counts = Dict(i => 0 for i in 1:n)
    visit_counts[current] = 1
    
    for step in 1:num_steps
        neighbors = findall(x -> x > 0.5, adjacency[current, :])
        
        if isempty(neighbors)
            break
        end
        
        current = rand(neighbors)
        push!(path, current)
        visit_counts[current] += 1
    end
    
    # Estimate stationary distribution
    stationary = Dict(i => visit_counts[i] / length(path) for i in 1:n)
    
    return RandomWalkAnalysis(
        start,
        current,
        path,
        visit_counts,
        num_steps,
        stationary
    )
end

# ============================================================================
# Part 2: Metropolis-Hastings Path Sampling
# ============================================================================

"""
    sample_proof_paths(adjacency::Matrix, num_samples::Int) -> Vector{Vector{Int}}

Sample paths via Metropolis-Hastings on proof dependency graph.

Uses spectral gap information to guide sampling toward mixing-optimal paths.

Args:
  - adjacency: Proof dependency adjacency matrix
  - num_samples: Number of paths to sample

Returns:
  - Vector of sampled paths
"""
function sample_proof_paths(adjacency::Matrix, num_samples::Int)
    n = size(adjacency, 1)
    paths = []
    
    for _ in 1:num_samples
        start = rand(1:n)
        walk = simulate_random_walk(adjacency, start, min(n + 5, 20))
        push!(paths, walk.visited_path)
    end
    
    return paths
end

# ============================================================================
# Part 3: Comprehension-Based Theorem Discovery (Bumpus style)
# ============================================================================

"""
    comprehension_discovery(adjacency::Matrix, spectral_gap::Float64) -> Dict

Discover theorems via random walk comprehension.

Benjamin Merlin Bumpus approach: Use mixing properties to identify
"comprehension regions" - sets of theorems that are frequently reached
together via random walks.

Args:
  - adjacency: Proof dependency graph
  - spectral_gap: From SpectralAnalyzer

Returns:
  - Dict with comprehension regions and connectivity
"""
function comprehension_discovery(adjacency::Matrix, spectral_gap::Float64)
    n = size(adjacency, 1)
    
    # Run multiple long walks to find comprehension regions
    mixing_time = estimate_mixing_time(spectral_gap, n)
    num_walks = max(10, Int(ceil(mixing_time)))
    
    co_visit_matrix = zeros(Float64, n, n)
    
    for _ in 1:num_walks
        start = rand(1:n)
        walk = simulate_random_walk(adjacency, start, Int(ceil(mixing_time)))

        # Record co-visitation (theorems visited in same walk)
        path = walk.visited_path
        for i in 1:length(path)
            for j in i+1:min(i+5, length(path))
                co_visit_matrix[path[i], path[j]] += 1.0
                co_visit_matrix[path[j], path[i]] += 1.0
            end
        end
    end
    
    # Identify comprehension regions via clustering
    comprehension_regions = Dict()
    threshold = quantile(vec(co_visit_matrix[co_visit_matrix .> 0]), 0.75)
    
    for i in 1:n
        region = findall(x -> x >= threshold, co_visit_matrix[i, :])
        if !isempty(region)
            comprehension_regions[i] = region
        end
    end
    
    return Dict(
        "comprehension_regions" => comprehension_regions,
        "mixing_time" => mixing_time,
        "avg_co_visitation" => mean(co_visit_matrix[co_visit_matrix .> 0]),
        "spectral_gap" => spectral_gap
    )
end

# ============================================================================
# Part 4: Reporting
# ============================================================================

function generate_random_walk_report(adjacency::Matrix, spectral_gap::Float64)
    n = size(adjacency, 1)
    mixing_time = estimate_mixing_time(spectral_gap, n)
    
    # Run sample walk
    sample_walk = simulate_random_walk(adjacency, 1, min(n * 2, 50))
    
    # Comprehension analysis
    comprehension = comprehension_discovery(adjacency, spectral_gap)
    
    report = """
╔════════════════════════════════════════════════════════════════════════╗
║            SPECTRAL RANDOM WALK ANALYSIS REPORT                       ║
║         Integrating Spectral Gaps with Random Walk Theory              ║
║              Benjamin Merlin Bumpus Comprehension Model                ║
╚════════════════════════════════════════════════════════════════════════╝

SPECTRAL PROPERTIES
═════════════════════════════════════════════════════════════════════════

  Spectral Gap:           $(round(spectral_gap, digits=4))
  Graph Size:             $n nodes (theorems)
  
RANDOM WALK MIXING
═════════════════════════════════════════════════════════════════════════

  Estimated Mixing Time:  $(round(mixing_time, digits=2)) steps
  Interpretation:         Random walk reaches stationary
                          distribution in ~$(Int(ceil(mixing_time))) steps
  
  Mixing Quality:         $(spectral_gap >= 0.25 ? "FAST (Ramanujan)" : "SLOW (tangled)")

SAMPLE WALK TRAJECTORY
═════════════════════════════════════════════════════════════════════════

  Starting node:          $(sample_walk.start_node)
  Path length:            $(length(sample_walk.visited_path))
  Unique nodes visited:   $(length(sample_walk.visit_counts))
  Coverage:               $(round(100 * length(sample_walk.visit_counts) / n, digits=1))%
  
  Path: $(join(sample_walk.visited_path[1:min(10, length(sample_walk.visited_path))], "→"))...

COMPREHENSION REGIONS (Bumpus Model)
═════════════════════════════════════════════════════════════════════════

  Comprehension regions found: $(length(comprehension["comprehension_regions"]))
  Average co-visitation rate:  $(round(comprehension["avg_co_visitation"], digits=2))
  
  These represent sets of theorems frequently accessed together
  via random walks - the "comprehension neighborhoods" of proof space.

IMPLICATIONS
═════════════════════════════════════════════════════════════════════════

  Fast mixing (high gap):    ✓ Good proof discoverability
  Slow mixing (low gap):     ✗ Tangled dependencies impede navigation
  
  Random walk on proof graph acts as a discovery mechanism for
  related theorems. Higher spectral gap → better exploration.

═════════════════════════════════════════════════════════════════════════
"""
    
    return report
end

end

if abspath(PROGRAM_FILE) == @__FILE__
    using .SpectralRandomWalk
    
    println("\n🎲 Spectral Random Walk Analysis - Proof Dependency Navigation\n")
    
    # Test graph: proof dependencies
    adjacency = [
        0 1 1 0 0
        1 0 1 1 0
        1 1 0 1 1
        0 1 1 0 1
        0 0 1 1 0
    ]
    
    # Compute spectral gap
    L = Diagonal(vec(sum(adjacency, dims=2))) - adjacency
    L_sym = Symmetric(L)
    eigenvalues = eigvals(L_sym)
    gap = eigenvalues[end] - eigenvalues[end-1]
    
    report = SpectralRandomWalk.generate_random_walk_report(Float64.(adjacency), gap)
    println(report)
    
    println("\n✓ Random walk analysis complete")
    println("  Mixing time determined by spectral gap")
    println("  Comprehension regions guide theorem discovery\n")
end
slack-gif-creatoranthropics/skillsKnowledge and utilities for creating animated GIFs optimized for Slack. Provides constraints, validation tools, and animation concepts. Use when users request animated GIFs for Slack like "make me a GIF of X doing Y for Slack."Stars: 198kUpdated Claude CodeCodexVerifiedInstall
ponytailDietrichGebert/ponytailLazy senior dev mode for any coding task: the smallest change that fully solves it, and a reply a busy human understands in one read.Stars: 194kUpdated Claude CodeCodexVerifiedInstall
ponytail-debtDietrichGebert/ponytailHarvest every shortcut: comment into one debt ledger, so deferrals get tracked instead of forgotten. One-shot report.Stars: 194kUpdated Claude CodeCodexVerifiedInstall
ponytail-debtDietrichGebert/ponytailList every `shortcut:` comment (and older `ponytail:` ones) as a debt ledger. One-shot report, changes nothing. Use for "ponytail debt", "what did ponytail defer", "list the shortcuts", /ponytail-debt.Stars: 194kUpdated Claude CodeCodexVerifiedInstall