# Random walk expected length

## Extimate the parameter $p$

$p$, it's the probability that during a walk, the successor of a given node it's a trap.

This is expensive to compute **during the walk** so we might approximate it computing the **Average** probability over all nodes.

For a given node $n$, with neighbours ${Ne}_n$, the campionary probability for the node to have traps as neighbours is:

$$
P(\text{Node $n$ has a trap neigbour}) = \frac{1}{|{Ne}_n|}\sum_{d\in {Ne}_n} \text{is_trap}(d)
$$

To have the probability that on any given graph a node has a trap as a neighbouring node, we need to compute the mean:

$$
\mathbb{E}[P(\text{Node $n$ has a trap neigbour})]= \frac{1}{|N|}\sum_{n\in N}\frac{1}{|{Ne}_n|}\sum_{d\in {Ne}_n} \text{is_trap}(d)
$$

For node_to_vec we can use:

$$
\mathbb{E}[P(\text{Node $n$ has a trap neigbour})]= \frac{1}{|N|}\sum_{n\in N}\sum_{n_i\in {Ne}_n} P_i \quad \text{is_trap}(d)
$$

where (TO CHECK FOR CORRECTNESS):
$$P_i = \frac{1}{\sum_j P_j}\left\{\begin{matrix}
1/q & src = dest\\
1/p & src \in Fs(dest)\\
1 & else
\end{matrix}\right.$$

Fs is the Forward-Star aka the neighbours of the given node.

We can use this value to compute the expected length of a random walk.

## Average random walk length

We need to compute the average length until a trap, therefore we need a geometric distribution.

$$\mathcal{G}(p, k) = p(1-p)^k$$

We need to estimate the quantile:

The Cumulative Distribution Function is:
$$1-\left(1-p\right)^{x}$$

Therefore the alpha-quantile can be computed as:

$$1-\left(1-p\right)^{k} = (1-\alpha)$$
$$\left(1-p\right)^{k} = \alpha$$
$$k \ln\left(1-p\right) = \ln(\alpha)$$

So we can compute the "alpha-quantile"

$$k = \frac{\ln(\alpha)}{\ln\left(1-p\right)}$$

we can define the "precision" $\beta = 1 - \alpha$ so:

$$k = \frac{\ln(1 - \beta)}{\ln\left(1-p\right)}$$

We can also derive that:

$$(1-p)^k = (1 - \beta)$$

So we can see that $\alpha$ is the probability that a random walk on the graph have length of at least $k$. And $\beta$ it's the complementary, so it's the probability that a random walk on the graph have length smaller than $k$.

## Choosing the Optimal precision $\beta$

### Time and Memory Analysis
We want to model the memory and time cost of an allocation strategy for the walks of a given graph.

The simple strategy we will analyze is just to allocate $k$ elements, and then if the walk excede this size, we reallocate the array with $L$ elements which is the max length of walks.

Reallocating is an expensive operation since (on the current libc implemnetation of jmalloc) if the next heap chunck it's occupied, the allocator is forced to allocate a new array and copy there the content and free the old array.

We denote $s_i$ is the length of the i-th walk. Denoting with $m(s_i)$ the memory required by the i-th walk.

## Memory analysis

Since the allocation strategy allocate $k$ elements and then, if the walk exceeds $k$ steps, we expand it to $L$, it's memory usage can be modeled as:

$$ m(s_i) = \left\{\begin{matrix}
k & s_i \le k\\
L & else
\end{matrix}\right.
$$

$$M(k) = \sum_i m(s_i)$$

$$M(s) = \sum_i k + \sum_j L = w(1-\beta) k + w\beta L$$

$$m(s) = (1-\beta) \frac{\ln(1 - \beta)}{\ln\left(1-p\right)} + \beta L$$

$$m(s) = \frac{1}{\ln(1-p)} \left[(1-\beta)\ln(1 - \beta) + \beta \ln\left((1-p)^L\right)\right]$$

$$m(s) = \frac{1}{\ln(1-p)} \left[(1-\beta)\ln(1 - \beta) \underbrace{+\beta\ln(\beta) -\beta\ln(\beta)}_0 + \beta \ln\left((1-p)^L\right)\right]$$

$$m(s) = \frac{1}{\ln(1-p)} \left[- H(\beta) -\beta\ln(\beta) + \beta \ln\left((1-p)^L\right)\right]$$

$$m(s) = \frac{1}{-\ln(1-p)} \left[ H(\beta) + \beta\ln(\beta) - \beta \ln\left((1-p)^L\right)\right]$$

$$m(s) = \frac{1}{-\ln(1-p)} \left[H(\beta) + \beta \ln\left(\frac{\beta}{(1-p)^L}\right)\right]$$

Since it's the entropy of a binary event, $0 \le H(\beta) \le 1$ so we can use 1 as upperbound.

$$m(s) \le \frac{1}{-\ln(1-p)} \left[1 + \beta \ln\left(\frac{\beta}{(1-p)^L}\right)\right]$$

Therefore the **final complexity** with regards to $\beta$ is:

$$m(s) = \mathcal{O}\left( \beta \ln\left(\frac{\beta}{(1-p)^L}\right)\right) = \mathcal{O}\left( \beta \ln\left(\beta\right)\right)$$

### Finding the optimal $\beta$ pt.1

It's to notice that since $0 \le \beta \le 1$:

$$ -\frac{1}{e} \le \beta \ln(\beta) \le 0$$

and the value of $\beta$ that minimize $\beta \ln(\beta)$ is $\beta = \frac{1}{e}$.

So we have the result:

$$m(s) \le \frac{1}{-\ln(1-p)} \left[1 + \beta \ln\left(\frac{\beta}{(1-p)^L}\right)\right]$$

$$m(s) \le \frac{1}{-\ln(1-p)} \left[1 + \beta \ln\left(\beta\right) - \beta \ln((1-p)^L)\right]$$

$$m(s) \le \frac{1}{-\ln(1-p)} \left[1 -\frac{1}{e} - \frac{1}{e} \ln((1-p)^L)\right]$$

$$m(s) \le \frac{(1 - \frac{1}{e}) - \frac{1}{e} L \ln(1-p)}{-\ln(1-p)}$$

$$m(s) \le \frac{1}{e} L + \frac{1 - \frac{1}{e}}{-\ln(1-p)}$$

### Finding the optimal $\beta$ pt.2

Another assignement of $\beta$ is $\beta = (1-p)^L$ then we get

$$m(s) = \frac{1}{-\ln(1-p)} \left[H(\beta) + \beta \ln\left(\frac{\beta}{\beta}\right)\right]$$

$$m(s) = \frac{H(\beta)}{-\ln(1-p)} \le \frac{1}{-\ln(1-p)}$$

The unit of measure is number of integers. Therefore if we multiply the bound by 64 we get the size in bits for modern systems.

### What $\beta$ to use and when

Let's find invert the disequation to know when to use which equation

$$ \frac{1}{e} L + \frac{1 - \frac{1}{e}}{-\ln(1-p)} \le \frac{1}{-\ln(1-p)}$$

$$ \frac{1}{e} L \le \frac{1}{-\ln(1-p)} - \frac{1 - \frac{1}{e}}{-\ln(1-p)}$$

$$ \frac{1}{e} L \le \frac{1 - (1 - \frac{1}{e})}{-\ln(1-p)} $$

$$ \frac{1}{e} L \le \frac{\frac{1}{e}}{-\ln(1-p)} $$

$$ L \le \frac{1}{-\ln(1-p)} $$

$$ -\ln(1-p)L \le 1 $$

$$ \ln\left(\frac{1}{(1-p)^L}\right) \le 1 $$

$$ \frac{1}{(1-p)^L} \le e $$

$$ (1-p)^L > \frac{1}{e} $$

Therefore if $(1-p)^L > \frac{1}{e}$ then it's best to use $\beta = \frac{1}{e}$ otherwise $\beta = (1-p)^L$.

Therefore:

$$\beta = \left\{\begin{matrix}
\frac{1}{e} & (1-p)^L > \frac{1}{e}\\
(1-p)^L & (1-p)^L \le \frac{1}{e}
\end{matrix}\right.$$

Which is equivalent to:

$$\beta = \min{\left\{\frac{1}{e}, (1-p)^L\right\}}$$

Therefore almost we will have $\beta = (1-p)^L$ since $\frac{1}{e} \approx 0.36787944$.

Moreover, it's easy to choose based on $p$, since the walk length we expect is around 80:
$$p = 1 -\sqrt[L]{\frac{1}{e}}$$
and
$$p = 1 -\sqrt[80]{\frac{1}{e}} = 1 - 0.9875778 = 0.0124222$$

Finally, for the expected walk length, if the trap_rate is over 1.24% then it's better to use $\beta = (1-p)^L$ .

The final result is that the optimal value is:

$$\beta = \min{\left\{\frac{1}{e}, (1-p)^L\right\}}$$

## Time analysis

Since the allocation strategy allocate $k$ elements and then, if the walk exceeds $k$ steps, we expand it to $L$, it's memory usage can be modeled as:

$$ t(s_i) = \left\{\begin{matrix}
k & s_i \le k\\
L + k & else
\end{matrix}\right.
$$

$$T(k) = \sum_i t(i)$$

We can greately simplify this formulations:

$$T(k) = \sum_i k + \sum_j (k + L) = w(1 - \beta) k + w\beta(k + L)$$

$$t(k) = (1 - \beta) \frac{\ln(1 - \beta)}{\ln\left(1-p\right)} + \beta\left(\frac{\ln(1 - \beta)}{\ln\left(1-p\right)} + L\right)$$

$$t(k) = \frac{1}{\ln\left(1-p\right)} \left[(1 - \beta) \ln(1 - \beta)+ \beta\ln(1 - \beta) + L\beta\ln\left(1-p\right)\right]$$

$$t(k) = \frac{1}{\ln\left(1-p\right)} \left[(1 - \beta) \ln(1 - \beta) + \underbrace{\beta \ln(\beta) - \beta \ln(\beta)}_0 + \beta\ln(1 - \beta) + L\beta\ln\left(1-p\right)\right]$$

$$t(k) = \frac{1}{\ln\left(1-p\right)} \left[-H(\beta) - \beta \ln(\beta) + \beta\ln(1 - \beta) + L\beta\ln\left(1-p\right)\right]$$

$$t(k) = \frac{1}{\ln\left(1-p\right)} \left[-H(\beta) + \beta\ln\left(\frac{1 - \beta}{\beta}\right) + \beta\ln\left((1-p)^L\right)\right]$$

$$t(k) \le \frac{1}{\ln\left(1-p\right)} \left[1 + \beta\ln\left(\frac{1 - \beta}{\beta}\right) + \beta\ln\left((1-p)^L\right)\right]$$

## Time with $\beta$ optimized for memory.

if $\beta = \frac{1}{e}$

$$t(k) \le \frac{1}{e}L + \frac{1.19912}{\ln(1-p)}$$

if $\beta = (1-p)^L$

$$t(k) \le \frac{1}{\ln(1-p)} + \frac{(1-p)^L \ln(1 - (1-p)^L)}{\ln(1-p)} \le \frac{1}{\ln(1-p)} + \frac{(1-p)^L}{\ln(1-p)}$$

$$t(k) \le \frac{1}{\ln(1-p)} + \frac{(1-p)^L}{\ln(1-p)} \le \frac{2}{\ln(1-p)}$$

# Parallel spanning tree algorithm

If we have $k$ thread and $n$ locked chunks, assuming that each thread has the same probability of choosing any chunk, the probability of "no-lock" aka the probability that each thread chooses a different chunk its:

$$ P(k, n) = \frac{\binom{n}{k}}{n^k} = \frac{\frac{n!}{k!(n - k)!}}{n^k} = \frac{n!}{k!n^k(n - k)!}$$

Therefore, we could set the value of this probability so that we can derive the number of chunks $k$

$$ P(k, n) = \alpha$$

It's difficult to find an analytical formulation of the quantile of order $\alpha$ so we did a polinomial regression on the quantile computed with order $0.97$.

The fidded polinomin is:
$$\Phi_{0.97}(k) = 0.68711485 -16.11782596 k +
16.41624929 k^2$$

And it fits really well:


I guesstimate that the optimal $\alpha$ is:
$$\alpha = \frac{T_\text{Lock wait}}{T_\text{Lock access}}$$

But we will have to formally prove this, this is similar to a weighted binary search.

The time is:
$$t = (1 - \alpha)\mathbb{E}[T] + \alpha L$$

$$\mathbb{E}[T] = \sum_{j=0}^{k} j \frac{\binom{n}{j}}{n^j}$$

# Fast extraction of random numbers in a range
The reminder operation is expensive so we are looking for ways to generate a batch random number in a range without using this operation.

One way would be Generating a random Elias-Fano, basically pre-computing the size of the high bits and the low bits, and then iter on its values. Here the only "caveat" is that we want exactly N ones in the high bits and for the last values if the low bits are all ones the value might be bigger than the max choosen.

Another nice feature we would want would be extracting distinct values.

# Random Dropout
Usually dropout has a fixed rate, why? It would be probabbly be better is the rate for each sample is extracted from a distribution.
The idea is that most of the time it will train like a normal dropout, but it will also sometimes it will learn almost without dropout which could improve the final performance without overfitting. Also having a possible high dropout examples could focus on "minor" features.

One easy way to implement this is to stack more dropout layer.

In a normal dropout layer with rate $\alpha$ the probability that **a single** output is $P(w_i = 0) = \alpha$.

Using the stacked Dropout using $n$ layers, all with rate $p$ is:
$$P(w_i = 0) = 1 - P(w_i \neq 0) = 1 - (1 - p)^n$$

So if we want to "equate" the normal layer we can set:

$$1 - (1 - p)^n = \alpha$$

$$- (1 - p)^n = \alpha - 1$$

$$(1 - p)^n = 1 - \alpha$$

$$(1 - p) = \sqrt[n]{1 - \alpha}$$

$$- p = \sqrt[n]{1 - \alpha} - 1$$

$$p = 1 - \sqrt[n]{1 - \alpha}$$

We have set things up so that each value has the same probability, what changes it's the propbability of how many values at zero are there.

For an input with $k$ values, the minimum case we have $\max \left(0, p k\right)$ are zero, In the maximum case it's $\min \left(k, p n k \right)1$

$$P\left ( \sum \left(w_i == 0\right) = x\right) = \frac{\binom{x}{kp}^{n}}{\binom{k}{kp}^n} = \left( \frac{\binom{x}{kp}}{\binom{k}{kp}}\right)^n $$

$$\binom{n}{k} = \frac{n!}{k!(n-k)!}$$

$$\frac{\binom{x}{a}}{\binom{k}{a}} = \frac{\frac{x!}{a!(x-a)!}}{\frac{k!}{a!(k-a)!}} = \frac{\frac{x!}{(x-a)!}}{\frac{k!}{(k-a)!}} = \frac{x!(k-a)!}{k!(x-a)!}$$

$$P\left ( \sum \left(w_i == 0\right) = x\right) = \left (\frac{x!(k-kp)!}{k!(x-kp)!} \right)^n$$

we could either implement a new layer or it can be approximated using multiple dropout layers sequentially. Basically the probability that multiple layers zero the same value is a binomial, which for n > 20 is approximable by a gaussian.

Approximating this way we get that the minimum rate we can have is $p$ and the biggest is $np$

Also, applying dropout on INPUT values, allows the model to learn to predict the values using a random subset of the features, and thus not overfocus on a single feature. This could improve the robustoness to noise.

# Lowerbound for linkprediction
We run a perceptron with in input only the degrees of the two nodes.
The degrees were normalized dividing by the max degrees so that they are in $[0, 1]$

This model acheived, on string PPI, performance:

loss: 0.4466
accuracy: 0.7921
recall: 0.7379
precision: 0.8276
AUROC: 0.8845
AUPRC: 0.8814
f1_score: 0.7802
balanced_accuracy: 0.7921
specificity: 0.8463
miss_rate: 0.2621
fall_out: 0.1537
mcc: 0.5876

and has weights:

[array([[0.00355815],
        [0.00372306]], dtype=float32),
 array([-1.9379908], dtype=float32)]

Thus it has a decision boundary of:

$$a + b >= 0.13$$

This prob is a pareto principle since the degrees follow a geometric distribution.

We would like to relate this value with the distribution parameters.

Also an interpretation in a probabilitstic framework would be nice.

# WORK WITH ERROS

## Pareto point deriviation

Pareto rule:

the 80% of land in Italy is owned by 20% of the peoples.

$$F(0.8) = 0.2$$

A general Pareto point is similar to a fixed point:

$$F(p) = 1 - p$$

Where $F(x) \in [0, 1] \quad x \in [0, 1]$ and $F(x + \epsilon) \ge F(x) \quad \forall \epsilon \ge 0$

We can notices that the cumulative distribution of any random variable $X \in [0, 1]$ satisfies this.

The cumulative distribution of a geometric is
$$1 - (1-p)^{k} = 1 - p$$

$$(1-p)^{k+1} = p$$

The solution for k is:

$$k = \frac{\log (p)}{\log(1 - p)}$$

## Formal anaylis

Probability that a random node $b$ is a neighbour of a random node $a$ with $n$ neighbours in a graph with \(V\) vertices is:

$$P(b \in N_a) = \frac{\binom{|V|}{n - 1}}{\binom{|V|}{n}}$$

We can hope for simplifications:
$$\binom{n}{k} = \frac{n!}{k!(n-k)!}$$

$$\frac{\binom{n}{k - 1}}{\binom{n}{k}} = \frac{\frac{n!}{(k-1)!(n-k+1)!}}{\frac{n!}{k!(n-k)!}} = \frac{k!(n-k)!}{(k-1)!(n-k+1)!} = \frac{k}{(n-k+1)}$$

So:

$$P(b \in N_a) = \frac{n}{|V|+1-n} \qquad n \in [0, |V|]$$

We can define $\nu = |V| + 1$

$$P(b \in N_a) = \frac{n}{\nu -n} \qquad n \in [0, \nu - 1]$$

$$P(b \in N_a) = -\frac{+\nu-\nu-n}{\nu - n} = \frac{\nu}{\nu - n}-1$$

We can know from experimental evidence that on biological graphs the node degrees are distributed as a power-law distribution:

$$n \sim \mathcal{P}_\theta(x)$$

Quindi ha senso calcolare?

$$P(b \in N_a) = \frac{n}{\nu -n} \mathcal{P}_\theta(n)$$

NO! questo e' uno step di bayes

$$P(A|B)=\frac{P(B|A)P(A)}{P(B)}$$

->

$$P(b \in N_a | b \sim \mathcal{P}_\theta) = \frac{P(b \sim \mathcal{P}_\theta | b \in N_a ) P(b \in N_a)}{P(b \sim \mathcal{P}_\theta)}$$

NAH THIS DON"T WORKS

### Tests

Not only, since the edge is un-directed, the node a must also be in the neighbourhood of a:

$$P(a, b) = P(b \in N_a)P(a \in N_b) = \frac{n_a}{\nu-n_a}\frac{n_b}{\nu-n_b}$$

$$P(a, b) = P(b \in N_a)P(a \in N_b) = \frac{n_a n_b}{(\nu-n_a)(\nu-n_b)}$$

$$P(a, b) = P(b \in N_a)P(a \in N_b) = \frac{n_a n_b}{\nu^2 + \nu(n_a + n_b) + n_a n_b}$$

Now the question is what distribution is $P(a, b) \sim ?$

I think that
$$n \sim (1 - p)^{|V| - n} p$$

## SUSS
If we want to sample $k$ values in the range $[0, n)$ we generate $k$ buckets of size $\frac{n}{k}$ and then we extract a single random value from each bucket.

For simplicity sake let's assume $k$ perfectly divide $n$.

This has less possible combinations than a true uniform:

$$|\mathcal{U}| = \binom{n}{k}$$

$$|\mathcal{B}| = \prod^k_{i=0} \frac{n}{k} = \left ( \frac{n}{k} \right )^k$$

So we might want to compute the ratio of how many combinations we cover:

$$\binom{n}{k} = \frac{n!}{k!(n-k)!}$$

$$\frac{|\mathcal{B}|}{|\mathcal{U}|} = \frac{\left ( \frac{n}{k} \right )^k}{\binom{n}{k}} = \frac{\left ( \frac{n}{k} \right )^k}{\frac{n!}{k!(n-k)!}} = \frac{n^k k! (n-k)!}{n! k^k} = \frac{n^k}{n!} \frac{k!}{k^k} (n-k)!$$

Stirling's approximation:
$$n! \sim_{n \to \infty} \sqrt{2 \pi n} \left( \frac{n}{e}\right)^n$$

$$ \frac{k!}{k^k} = \frac{\sqrt{2 \pi} \sqrt{k} k^k e^{-k}}{k^k} = \sqrt{2 \pi} \frac{\sqrt{k}}{e^{k}}$$

$$ \frac{n^k}{n!} = \frac{n^k}{\sqrt{2 \pi n} \left( \frac{n}{e}\right)^n} = \frac{1}{\sqrt{2 \pi}} \frac{n^{k - n}}{\sqrt{n}} e^{n}$$

$$(n - k)! = \sqrt{2 \pi}\sqrt{(n - k)} (n - k)^{(n - k)} e^{k - n}$$

$$\frac{k!}{k^k} \frac{n^k}{n!} = \sqrt{2 \pi} \frac{\sqrt{k}}{e^{-k}} \frac{1}{\sqrt{2 \pi}} n^{k - n} e^{n} = \frac{\sqrt{k}}{\sqrt{n}} n^{k - n} e^{n - k} $$

$$ \frac{k!}{k^k} \frac{n^k}{n!}(n - k)! = \frac{\sqrt{k}}{\sqrt{n}} n^{k - n} e^{n - k} \sqrt{2 \pi}\sqrt{(n - k)} (n - k)^{(n - k)} e^{k - n} $$

$$ \frac{\sqrt{k}}{\sqrt{n}} n^{k - n} \sqrt{2 \pi}\sqrt{(n - k)} (n - k)^{(n - k)} = \sqrt{2 \pi} \sqrt{\frac{k(n-k)}{n}} (n-k)^{(n-k)}$$

$$\frac{|\mathcal{B}|}{|\mathcal{U}|} \sim_{n \to \infty} \sqrt{2 \pi} \sqrt{\frac{k(n-k)}{n}} (n-k)^{(n-k)} \sim_{n >> k} \sqrt{2 \pi} \sqrt{k} (n-k)^{(n-k)} = \mathcal{O} \left (n^n \right )$$