Average-case space complexity I am trying to find problems whose average-case space complexity has been analyzed. 

More specifically, I am interested to know if there are any  problems with a proven  space complexity lower bound that is  super-linear, and especially if there are any  with an  average-case analysis (e.g., the bound holds even if the algorithm is allowed to err for a small percentage of times etc. )

Thanks in advance
I'm interested in but not familiar with this topic. Searching for "Average case complexity theory", I found a thesis written by Tomoyuki Yamakami:


  Average Case Computational Complexity Theory, Tomoyuki Yamakami, 1997.


Section 3.5.1 seems relevant, a space-analog notion similar to the average-time complexity is defined. Hopefully with a deeper reading we'll find some problems that has been analysed :)

Also in the paper


  On the Theory of Average Case Complexity, Shai Ben-David, Benny Chor, Oded Goldreich and Michael Luby, 1989.


Average log-space complexity is defined in Section 7.