# Randomized Submatrix of a Sparse Matrix

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:

1. generate a random number $$rand$$ such that $$0\le rand \le 1$$.
2. if $$(rand < p_{11}) \implies$$ add $$A_{11}$$ to $$B$$.
3. go to the next entry of $$A$$ and repeat from step $$1$$ until $$s$$ entries are 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.