I have a PTM with following transition:

$\delta(Z_0, \square , 0) = \delta(Z_0, \square , L, R)$,

$\delta(Z_0, \square , 1) = \delta(Z_0, \square , R, R)$

Suppose that this PTM executes n steps. What is the probability that the head has moved k steps to the right on the work tape (in total, i.e., k is the difference between moves to the right and moves to the left) ?

  • 2
    $\begingroup$ Welcome to the site! Help us help you: what have you done so far? what is unclear? what are your thoughts on the problem? We're not a "do my problems for me" site. $\endgroup$ May 7, 2020 at 23:07

1 Answer 1


It seems to me as first thought, it is the summation of all moves i to R, j to L where
( i+j = n) AND (i - j = k) which leads to
i =(n+k) /2

Assuming the prob of each step of the walk is indep. from the current position (I can't read the probs u r writing, the 2nd parameter is appearing as a square). So, it would be something like

Pij= (PR ^ i) * (PL ^ j)


(I'm talking probability, I do not have a fresh memory of Probabilistic Turing m/cs at the moment)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.