In July of 2010, Tomas Rokicki, Herbert Kociemba, Morley Davidson, and John Dethridge demonstrated (computationally) that a $3\times3\times3$ Rubik's cube, starting in an arbitrary configuration, can strictly be solved in at most 20 Singmaster moves (under the face-turn metric) from Rubik's Cube move group $(G, *)$, where $*$ is the concatenation operation (summarized here: https://en.wikipedia.org/wiki/Rubik%27s_Cube_group ). In 2011, Erik Demaine et. al. (Algorithms for Solving Rubik's Cubes, arXiv:1106.5736v1 ) showed that any ($n \times n \times n$) Rubik's cube can optimally be solved in $\Theta (\frac{n^2}{\log(n)})$ steps, also under the face-turn metric.
Say we restrict ourselves to the simpler quarter-turn metric (only allowing for 90 degree rotations), and set up the following scenario:
We hand a ($n \times n \times n$) Rubik's cube to a robot, and program the robot to execute an random set of 90 degree Singmaster moves in $G$, then stop when the cube is solved. We know that the number of total cube states for a $3\times3\times3$ cube is: $||G|| = (2^{27}.3^{14}.5^3.7^2.11) = 43,252,003,274,489,856,000$ (Turner and Gold 1985, Schonert), and we can therefore use the negative binomial distribution calculate the mean number of random system states we need to sample to find a "finished" cube (call this value $S_3$ for the $3\times3\times3$ cube and $S_n$ for the $n \times n \times n$ cube). However, the robot is performing random quarter-turn moves, not necessarily randomly sampling cube configurations.
What distribution can we expect for the number of random 90 degree Singmaster moves necessary for the robot to complete the cube? I suppose we can calculate an upperbound for the expected mean number of required moves by taking a product of $S_n$ and the mean number of random moves necessary to "mix" the cube (I'm unaware of an estimate for this time), but can we do better? Also, I would guess that the "mixing time" for the cube is much faster than the solution time, making it the case that the initial state of the cube shouldn't matter.
(I'm not entirely opposed to allowing for arbitrary 90 or 180 degree Singmaster moves by the robot, but it just seems simpler to only consider the set of quarter-turn moves.)
Update :: Based on Brendan McKay's answer, which I mostly agree with, I intuitively feel that that the number of steps to find a solution for a ($n \times n \times n$) cube via a random walk on the cube's Cayley graph, should be something like $\Theta (||G|| \log (||G||))$. This intuition is coming from the scaling for the expected coverage time for a random walk on an integer lattice.
From: Jonasson, J., Schramm, O. On the cover time of planar graphs. Electronic Communications in Probability 5, pp. 85 – 90 (2000), we have that the cover time for a $d$-dimensional integer lattice $G$ with $n$ vertices scales as: $\Theta(n^2)$ for $d = 1$, $\Theta(n (\log n)^2)$ for $d = 2$, and $\Theta(n \log n)$ for $d \geq 3$. (hat tip to Andreas Rüdinger for his answer to Expected number of steps for a discrete random walk to visit every point on an N-dimensional rectangular lattice).
For the Cayley graph of a generalized Rubik's cube, it seems like we're in the limit of the sort of connectivity on an integer lattice that yields $\Theta(n \log n)$ covering times. So I suppose, on average, it should take about half this many steps to find the solved cube configuration?
Obviously this is very very sketchy reasoning, and I hesitate to actually write it down.
Best Answer
I think the expected time for stumbling across the solution is roughly proportional to the number of configurations. The process you describe is walking randomly on a Cayley graph. The limiting distribution is uniform, so after a large number of steps you will be in approximately a random place and the chance of that being the solution is the reciprocal of the number of vertices (i.e. the number of configurations). If someone expert in rapid mixing of Markov chains comes along, they will tell us if this argument can be made rigorous.
ADDED: This much is certain: Say $N$ is the number of configurations. If you start at a random configuration, then the probability of being at the solution configuration after $i$ steps is exactly $1/N$ for every $i$. However these are not independent events. The expected number of solutions seen in the first $N$ steps is exactly 1, but it does not follow that the expected wait for the first solution is $N$.