Creation of MxM matrix: Python version much slower than Matlab version
You use very short variable names, so its hard to follow what your code is doing.

For speed in numpy, you need to use vector operations. So instead of writing

for ii in range(step):
    out[ii] = ii * x + b


You should write:

out = numpy.arange(step)*x + b


Individually accessing the elements of numpy array is actually quite slow. You need to write your code to do everything in vector operations.

Here is my rewrite of your inner loop to be vectorized. You could vectorize the outer loop as well, but this should make the biggest difference.

        f1 = int(bb[k][0])
        f2 = int(bb[k][1])  
        f3 = int(bb[k][2])
        f4 = int(bb[k][3])

        ptj = np.arange(step_prob, 1.0 + step_prob, step_prob)[:, None]
        pfj = np.arange(step_prob, 1.0 + step_prob, step_prob)[None, :]

        out_t = f1*pti*ptj+f2*pti*(1-ptj)+f3*(1-pti)*ptj+f4*(1-pti)*(1-ptj)
        out_f = f1*pfi*pfj+f2*pfi*(1-pfj)+f3*(1-pfi)*pfj+f4*(1-pfi)*(1-pfj)
        sj = (1 - pfj + ptj) / 2

        the_max = np.maximum(sj, [si])
        s = ((1-out_f+out_t)/2)-the_max

        temp = s*(s&gt;0)*np.tril(np.ones((len(s),len(s))).astype(int))
        improve[ii-1,jj-1]=improve[ii-1,jj-1]+temp.sum()