Methods and apparatuses for performing arithmetic encoding and/or decoding are disclosed. In one embodiment, the method for creating a state machine for probability estimation comprises assigning probabilities to states of a look up table (LUT), including setting a probability for each state i of the states equal to the highest probability of the LPS multiplied by the adaptation rate to the power i, where i is a number for a given state and the adaptation rate is smaller than 1. The method also comprises generating state transitions for states in the LUT to be transitioned to upon observing an MPS and an LPS, wherein the next state to which the state machine transitions from a current state when an MPS is observed is a next state higher than the current state if the current state is not the highest state and is the current state if the current state is the highest state. Furthermore, the next state to which the state machine transitions from a current state when an LPS is observed for a plurality of states is a rounded version of a result of calculating:
number of current state+log((probability of the current state*the adaptation rate+(1−the adaptation rate))/probability of the current state)/log(the adaptation rate).