# Recent MathOverflow Questions

### Likelihood function to estimate the randomness parameter in Watts and Strogatz's model (1998)

Math Overflow Recent Questions - Mon, 03/04/2019 - 05:42

Consider the Watts and Strogatz's model (W&S, 1998) with randomness parameter $p$, where $0\leq p\leq 1$. Suppose one observes the adjacency matrix of an undirected, unweighted social network after rewiring.

Problem: Derive the likelihood function of $p$ associated with this observed social network to estimate $p$ via maximum likelihood.

Below I propose a solution to obtain this likelihood function. This solution uses arguments provided in Menezes et al. (2017). In this solution, there are two points (labeled as Point 1 and Point 2) where I am not sure whether the rationale is correct or not. I was wondering if you could help me with these two points, please. For each point that is not correct, if any, please let me know where I am wrong and why. Thanks a lot for your help and suggestions.

Notation:

$N$: size of the social network, i.e. its number of nodes.

$p$: randomness parameter in W&S.

$k$: number of right-side neighbors of any node in the regular lattice, i.e. when $p=0$; therefore, the input of W&S is the regular lattice of size $N$, where each node is connected with its $2\cdot k$ closest neighbors.

$[i$-$j]$: arc that connects nodes $i$ and $j$, with $(i,\,j)\in\{1,\ldots,\,N\}^2$.

$A_{i,\,j}$: binary random variable such that, before rewiring, $A_{i,\,j}=1$ if $[i$-$j]$ exists and $A_{i,\,j}=0$ otherwise, where $\mathbb{P}(A_{i,\,j}=1)=2\cdot k/(N-1)$.

$A_{i,\,j}^{(p)}$: binary random variable such that, after rewiring based on W&S with randomness parameter $p$, $A_{i,\,j}^{(p)}=1$ if $[i$-$j]$ exists and $A_{i,\,j}^{(p)}=0$ otherwise.

In an unweighted, undirected social network, one observes $A_{i,\,j}^{(p)}=a_{i,\,j}^{(p)}$, with $a_{i,\,j}^{(p)}\in\{0,\,1\}$ for all $(i,\,j)$, $A_{i,\,i}^{(p)}=0$ for all $i$, and $A_{i,\,j}^{(p)}=A_{j,\,i}^{(p)}$ for all $(i,\,j)$.

Thus, the likelihood function of $p$ associated with the observed social network is $$\mathcal{L}(p\,|\,\{a_{i,\,j}^{(p)}:\,i<j\})=\prod_{i<j}\mathbb{P}(A_{i,\,j}^{(p)}=a_{i,\,j}^{(p)}),$$ where $a_{i,\,j}^{(p)}\in\{0,\,1\}$ for all $(i,\,j)$, with $i<j$. Note that

$$\mathbb{P}(A_{i,\,j}^{(p)}=0)=\mathbb{P}(A_{i,\,j}^{(p)}=0\,|\,A_{i,\,j}=1)\cdot\mathbb{P}(A_{i,\,j}=1)+\mathbb{P}(A_{i,\,j}^{(p)}=0\,|\,A_{i,\,j}=0)\cdot\mathbb{P}(A_{i,\,j}=0),$$ where $\mathbb{P}(A_{i,\,j}=1)=1-\mathbb{P}(A_{i,\,j}=0)=2\cdot k/(N-1)$.

Point 1: Consider the following rationale to compute $\mathbb{P}(A_{i,\,j}^{(p)}=0\,|\,A_{i,\,j}=1)$:

To compute $\mathbb{P}(A_{i,\,j}^{(p)}=0\,|\,A_{i,\,j}=1)$, note that one chooses $[i$-$j]$ for rewiring with probability $p$. Next, one chooses one extreme of the arc associated with either node $i$ or node $j$ with probability $1/2$ each. Next, with probability $(N-1-2\cdot k)/N$ one rewires the chosen extreme of the arc to any node in the network except (a) the node associated with the opposite extreme and (b) any of its $2\cdot k$ closest neighbors. Therefore, $$\mathbb{P}(A_{i,\,j}^{(p)}=0\,|\,A_{i,\,j}=1)=p\cdot(1/2+1/2)\cdot(N-1-2\cdot k)/N=p\cdot(N-1-2\cdot k)/N.$$ Point 1 question: Is this rationale correct?

Point 2: Consider the following rationale to compute $\mathbb{P}(A_{i,\,j}^{(p)}=1\,|\,A_{i,\,j}=0)$:

To compute $\mathbb{P}(A_{i,\,j}^{(p)}=1\,|\,A_{i,\,j}=0)$, consider a node $u\notin\{i,\,j\}$, such that either $[i$-$u]$ or $[j$-$u]$ exists. Lets consider $[i$-$u]$ (resp., $[j$-$u]$). One chooses this arc for rewiring with probability $p$. Next, with probability $1/N$ one chooses the node $j$ (resp. $i$) to produce $[i$-$j]$. Therefore, $$\mathbb{P}(A_{i,\,j}^{(p)}=1\,|\,A_{i,\,j}=0)=2\cdot p\cdot 1/N.$$ Point 2 question: Is this rationale correct?

Finally, for all $i<j$, $$\mathbb{P}(A_{i,\,j}^{(p)}=0)=2\cdot k/(N-1)\cdot p\cdot (N-1-2\cdot k)/N+(1-2\cdot k/(N-1))\cdot(1-2\cdot p/N)$$ and $\mathbb{P}(A_{i,\,j}^{(p)}=1)=1-\mathbb{P}(A_{i,\,j}^{(p)}=0)$.

As a result, one can obtain the likelihood function to estimate $p$ via maximum likelihood.

References

Menezes, M. B., Kim, S., & Huang, R. (2017). Constructing a Watts-Strogatz network from a small-world network with symmetric degree distribution. PloS one, 12(6), e0179120.

Watts, D. J., & Strogatz, S. H. (1998). Collective dynamics of ‘small-world’ networks. Nature, 393(6684), 440.

### What role do Hecke operators and ideal classes perform in "Quantum Money from Modular Forms?"

Math Overflow Recent Questions - Sun, 03/03/2019 - 21:31

Cross-posted on QCSE

An interesting application of the no-cloning theorem of quantum mechanics/quantum computing is embodied in so-called quantum money - qubits in theoretically unforgeable states. The initial ideas from the landmark work in the '70s/'80s require a bank to verify each transaction. Accordingly public key quantum money was introduced in the late 2000's.