I have a sparse square matrix $A$ with size $n \times n$ and number of nonzero entries $nnz$. The goal is making a sub-matrix $B$ with $s$ nonzeros which are randomly chosen from $A$. Duplicates are ok, so we need at most $s$ nonzeros in $B$.
The probability of entry $A_{kl}$ being chosen is $p_{ij} = \frac{A_{ij}^2}{\sum_{k, l} A_{kl}^2}$, in which, $k$ and $l$ go through all the matrix entries. I have this algorithm in mind so far:
- generate a random number $rand$ such that $0<= rand <= 1$.
- if(rand < p_11) add $A_{11}$ to B.
- go to the next entry of A and repeat from step $1$ until $s$ entries is chosen.
If I go through all entries of $A$ once, on average how many entries will be chosen? In other words, how many times I should go through entries of $A$ to have $s$ entries chosen? I want to change the probability $p_{ij}$ so by going through entries of A once, all $s$ entries are chosen.