svd_pow.jl

# "Find a full-rank matrix with smallest singular value less than X."
# Question: is this a good way to do proof-of-work?

using Winston
using Distributions

function svd_work(N, target)
    tic()
    while true
        A = rand(N, N)
        A ./= sum(A, 1)
        S = last(svdfact(A)[:S])
        if S <= target
            break
        end
    end
    toq()
end

# Collect some data
num_trials = 10000
N = 100
target = 0.001
time_elapsed = (Float64)[]
for i = 1:num_trials
    push!(time_elapsed, svd_work(N, target))
end

# Is this a Poisson process?
# Look for exponentially distributed arrival times
nbins = 50
edges, counts = hist(time_elapsed, nbins)

# Get scale parameter using MLE
θ = fit_mle(Exponential, time_elapsed).scale
exp_counts = exp(-edges / θ) / θ

# Normalize to probabilities
counts /= sum(counts)
exp_counts /= sum(exp_counts)

# Plot results
P = FramedPlot(title="SVD-POW",
               xlabel="time elapsed (seconds)",
               ylabel="probability")
add(P, Points(edges, counts, color="blue"))
add(P, Curve(edges, exp_counts, color="red"))
setattr(P.y1, "log", true)
setattr(P.y2, "log", true)
setattr(P.x1, "log", true)
setattr(P.x2, "log", true)
file(P, "svd-pow.png")