All I have in hand is a adjacency matrix of a digraph with equal weight on every edge, is there a very simple way to convert this to a state change probability matrix?

  • $\begingroup$ Yes. What have you tried? $\endgroup$ – Yuval Filmus Nov 21 '16 at 21:02
  • $\begingroup$ the standard way that i'm doing is to sum each row and then divide the row by the sum, like [[0,1,1],[1,0,0],[1,1,0]] became [[0,1/2,1/2],[1,0,0],[1/2,1/2,0]]. But i got myself thinking if theres any way to do it faster $\endgroup$ – Henrique Almeida Marcomini Nov 21 '16 at 21:32
  • $\begingroup$ This already runs in linear time, and since (virtually) all entries have to be updated, you can't really do any better. $\endgroup$ – Yuval Filmus Nov 21 '16 at 22:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.