What you write inside Animate should follow the same guidelines as what you would put inside a Dynamic, because in the end it transforms to a dynamic box. The same happens for Manipulate.
When you are creating some dynamic output, you should ask yourself "if after running this, it was run again, would the output change?". If it would change, then you are in trouble because Mathematica will evaluate it again and again endlessly.
x=0;Dynamic[++x]
Your case with AppendTo is similar. You are not only not getting the result you want but are getting continuous updates, wasting CPU. And these updates have nothing to do with i being changed from 1 to 100, they are due to your own manual updates on m and k.
Even when, as @MrWizard suggested, you can fix your code by adding TrackedSymbols to prevent the endless recursion, I believe as a general rule it's a workaround you should try not to appeal to, unless other things fail. That is because Mathematica tries not to perform useless dynamic updates, but in general it doesn't guarantee it won't. I often come into dynamic code that does a couple of extra useless updates that I wouldn't expect. If your code's proper functioning depends on those unexpected updates not happening, you can end up with the occasional surprise.
Furthermore, dynamic updates may not happen when the control isn't visible on the screen, but the Animator's i variable will keep on moving forward, missing some udpates. Try minimizing the window in your question or MrWizard's answer while running the animation to see what happens. Also, if one dynamic update ends up taking too long you will also end up missing the next one.
How I'd do it
What do you want to see?
a plot with the coin flip results up to time i and a line with the partial means?
Do you want new values in each animation repetition? You want the animation to go to infinity or just to a predefined value? Let's assume you want it to infinity.
So,
whatYouWantToSee[results_List] :=
Show[ListPlot[results, PlotStyle -> PointSize[Large]],
ListLinePlot[cumulativeMeans@results], AxesOrigin -> {1, 0}];
While I was writing this, I got lazy and called cumulativeMeans instead of coding it: let it be a problem for future Rojo. But the future has come
cumulativeMeans[results_List] := Accumulate@results/Range@Length@results // N
Now, how do we generate the result list based on the time?
We need to generate a new coin result for every time, but only the first time the function is called for that particular time. That can be achieved through memoization. You can search the forum for more insight, there's a lot
ClearAll[coinResult];
SetAttributes[coinResult, Listable];
coinResult[i_] := coinResult[i] = RandomInteger[];
Finally
Animate[whatYouWantToSee@coinResult@Range@i, {i, 1, Infinity, 1}, AnimationRate -> 1]
See that the output of whatYouWantToSee@coinResult@Range@i won't change whether we run it 1 or 100 times. That's the main difference between the solutions
EDIT
Say you just want to see one repetition of 100 coin tosses. Now you can do without all that memoization and do something simpler. Just generate the list of results
coinResultList = RandomInteger[{0, 1}, 100];
and then
Animate[whatYouWantToSee@coinResultList[[;; i]], {i, 1, 100, 1},
AnimationRate -> 1]
Note that this would be more or less equivalent to using ListAnimate
ListAnimate[Table[whatYouWantToSee@coinResultList[[;; i]], {i, 100}],
AnimationRate -> 1]
The moral here is that until i changes, whatYouWantToSee@coinResultList[[;; i]] will always return the same result. Notice that this would have NOT been the case if you had done
Animate[whatYouWantToSee@RandomInteger[{0, 1}, 100][[;; i]], {i, 1,
100, 1}, AnimationRate -> 1]
